7986: BZOJ3986:Tree and Sets
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
有一棵n个结点的树,每条边有个长度leni (1≤leni≤10000)。 有q个点集,每个点集给定两个整数u,d (1≤u≤n,1≤d≤109),表示所有与u的距离不超过d的点(包括u)在这个点集中。 两个点之间的距离为它们之间的最短路径的长度。 要求构造一个DAG(有向无环图),满足: 1、这个DAG至少有n+q个点,至多有1200000(1.2×106)个点和2400000(2.4×106)条边 2、对于每一条边u→v,u>n 且 u≠v 3、对于第i (1≤i≤q)个点集的每一个点x,第n+i个点到第x个点都有且仅有一条路径 4、对于不在第i (1≤i≤q)个点集的每一个点x,第n+i个点到第x个点都不存在路径 由于一些奇怪的原因,树上可能多了若干条边,但是这些边覆盖的树链不会重合,且不会存在自环。(即这棵树是仙人掌)
输入格式
第一行三个整数n,m,q,其中m表示这棵仙人掌上一共有m条边。 接下来m行,每行三个整数u,v,len,表示u和v之间有一条长度为len的无向边。 接下来q行,每行两个整数u,d,第i行表示第i个点集。
输出格式
第一行两个整数V,E,表示你构造的DAG的点数和边数。 接下来E行,每行两个整数u,v,表示u到v有一条有向边。 !!!请注意输出文件的大小,不能超过32MB,否则会显示TLE!!!
样例输入
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
提示
N<=10000,N-1<=m<=2*N-2,Q<=10000
尚无SPJ,请不要提交!
题目来源
2015年集训队互测