#P11732. [集训队互测 2015] Tree and Sets(暂无 Special Judge)

    ID: 13100 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2015点分治集训队互测Special Judge分治仙人掌

[集训队互测 2015] Tree and Sets(暂无 Special Judge)

题目描述

wangyisong1996 有一棵小树苗,可惜由于土地沙漠化小树苗枯死了。正当 wangyisong1996 悲痛欲绝的时候,从沙子中长出了一棵仙人掌。

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

有一棵 nn 个结点的仙人掌,每条边有一个长度 ll。(不同的边的长度不一定相同)

qq 个点集,每个点集可以用两个整数 u,du, d 来描述(1un1 \leq u \leq n),一个结点 vv 在这个点集中当且仅当结点 vv 与结点 uu 的距离不超过 dd。两个结点之间的距离为它们之间的最短路径的长度。

现在要求构造一个有向无环图(DAG),满足:

  1. 这个 DAG 至少有 n+qn+q 个结点,至多有 12000001200000 个结点和 24000002400000 条边。
  2. 对于每一条边,如果是从 uu 连向 vv 的,那么 u>nu > nuvu \neq v
  3. 对于结点编号在第 ii 个点集(1iq1 \leq i \leq q)的每一个结点 xx,第 n+in+i 个结点到第 xx 个结点有且仅有一条路径。
  4. 对于结点编号在 {1,2,,n}\{ 1, 2, \dots, n\} 中但不在第 ii 个点集(1iq1 \leq i \leq q)的每一个结点 xx,不存在第 n+in+i 个结点到第 xx 个结点的路径。

输入格式

第一行三个正整数 n,m,qn, m, q,其中 n,mn, m 表示这棵仙人掌一共有 nn 个结点 mm 条边。

接下来 mm 行,每行三个整数 u,v,lu,v,l,表示 uuvv 之间有一条长度为 ll 的无向边。保证 1u,vn1 \leq u, v \leq n

接下来 qq 行,第 ii 行表示第 ii 个点集,用两个整数 u,du, d 来描述,保证 1un1 \leq u \leq n

输出格式

第一行两个非负整数 V,EV,E,表示你构造的 DAG 的点数和边数。

接下来 EE 行,每行两个整数 u,vu,v,表示 uuvv 有一条有向边。你需要保证 1u,vV1 \leq u, v \leq V

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

提示

测试点编号 nn mm qq
1 =1000= 1000 m=n1m = n - 1 =1000= 1000
2 =10000= 10000 =10000= 10000
3 =10000=10000
4 =9000= 9000 =9000= 9000
5 =10000= 10000 =10000= 10000
6 =1000= 1000 n1m2n2n - 1 \leq m \leq 2n - 2 =1000= 1000
7 =10000= 10000 =10000= 10000
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) 表示区间 [l,r)[l,r) 中的所有数,randint(l,r) 返回一个在 [l,r][l,r] 内的随机整数。

addedge(u, v) 表示在 uuvv 间连一条边。(边的长度的生成方式,你以为我会告诉你吗?)