#P11732. [集训队互测 2015] Tree and Sets(暂无 Special Judge)
[集训队互测 2015] Tree and Sets(暂无 Special Judge)
题目描述
wangyisong1996 有一棵小树苗,可惜由于土地沙漠化小树苗枯死了。正当 wangyisong1996 悲痛欲绝的时候,从沙子中长出了一棵仙人掌。
如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。
有一棵 个结点的仙人掌,每条边有一个长度 。(不同的边的长度不一定相同)
有 个点集,每个点集可以用两个整数 来描述(),一个结点 在这个点集中当且仅当结点 与结点 的距离不超过 。两个结点之间的距离为它们之间的最短路径的长度。
现在要求构造一个有向无环图(DAG),满足:
- 这个 DAG 至少有 个结点,至多有 个结点和 条边。
- 对于每一条边,如果是从 连向 的,那么 且 。
- 对于结点编号在第 个点集()的每一个结点 ,第 个结点到第 个结点有且仅有一条路径。
- 对于结点编号在 中但不在第 个点集()的每一个结点 ,不存在第 个结点到第 个结点的路径。
输入格式
第一行三个正整数 ,其中 表示这棵仙人掌一共有 个结点 条边。
接下来 行,每行三个整数 ,表示 和 之间有一条长度为 的无向边。保证 。
接下来 行,第 行表示第 个点集,用两个整数 来描述,保证 。
输出格式
第一行两个非负整数 ,表示你构造的 DAG 的点数和边数。
接下来 行,每行两个整数 ,表示 到 有一条有向边。你需要保证 。
10 9 5
2 1 9553
3 2 8499
4 3 5171
5 1 7123
6 3 1904
7 5 5526
8 7 5853
9 6 6635
10 8 7858
6 4981
7 14400
3 21290
4 9451
10 16609
15 19
11 6
11 3
12 7
12 5
12 1
12 8
12 10
13 3
13 6
13 9
13 4
13 2
13 1
14 4
14 3
14 6
15 10
15 8
15 7
提示
测试点编号 | |||
---|---|---|---|
1 | |||
2 | |||
3 | |||
4 | |||
5 | |||
6 | |||
7 | |||
8 | |||
9 | |||
10 |
第 2 个测试点的生成方式:
for i in range(2, 10001):
addedge(i, i / 2)
第 3 个测试点的生成方式:
for i in range(2, 5000):
addedge(i, i - 1)
for i in range(5000, 10001):
addedge(i, randint(1, i - 1))
其中 range(l,r)
表示区间 中的所有数,randint(l,r)
返回一个在 内的随机整数。
addedge(u, v)
表示在 和 间连一条边。(边的长度的生成方式,你以为我会告诉你吗?)