首页 > 代码库 > [CodeVS]1638 修复公路
[CodeVS]1638 修复公路
题目描述 Description
A地区在地震过后,连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出A地区的村庄数N,和公路数M,公路是双向的。并告诉你每条公路的连着哪两个村庄,并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车,即最早什么时候任意两条村庄都存在至少一条修复完成的道路(可以由多条公路连成一条道路)
输入描述 Input Description
第1行两个正整数N,M(N<=1000,M<=100000)
下面M行,每行3个正整数x, y, t,告诉你这条公路连着x,y两个村庄,在时间t时能修复完成这条公路。(x<=N,y<=N,t<=100000)
输出描述 Output Description
如果全部公路修复完毕仍然存在两个村庄无法通车,则输出-1,否则输出最早什么时候任意两个村庄能够通车。
样例输入 Sample Input
4 4
1 2 6
1 3 4
1 4 5
4 2 3
样例输出 Sample Output
5
对于这道题,蒟蒻的想法就是直接并查集,然后最后取最大值
具体如下
题意好像是这样的吧:
就是说告诉你x,y之间有一条边相连,当然你也可以选择无视他,然后呢边上权值就是v[i]了吗,所以我们就可以用一个快排从小到大吧权值排一遍,然后呢每次判断如果x,y点没有在一个集合内就连起来,
因为说修理这些路是可以同时进行的,所以我们只需要把最大值输出就行了,当然,在此之前要先判断每两个点是否有边相连,具体请看蒟蒻代码
1 //uses math; 2 var i,j,n,m,ans,maxans:longint; 3 x,y,t:array[1..1000]of longint; 4 pre:array[1..1000]of longint; 5 function max(a,b:longint):longint; 6 begin 7 if a>b then exit(a); 8 exit(b); 9 end; 10 function find(x:longint):longint; 11 begin 12 if pre[x]=x then exit(x); 13 find:=find(pre[x]); 14 pre[x]:=find; 15 end; 16 procedure join(x,y:longint); 17 var fx,fy:longint; 18 begin 19 fx:=find(x);fy:=find(y); 20 if fx<>fy then pre[fx]:=find(fy); 21 end; 22 function judge(x,y:longint):boolean; 23 var fx,fy:longint; 24 begin 25 fx:=find(x);fy:=find(y); 26 if fx<>fy then exit(false); 27 exit(true); 28 end; 29 procedure kp(l,r:longint); 30 var i,j:longint; 31 var mid,a:longint; 32 begin 33 i:=l; 34 j:=r; 35 mid:=t[(l+r)div 2]; 36 repeat 37 while t[i]<mid do inc(i); 38 while t[j]>mid do dec(j); 39 if i<=j then 40 begin 41 a:=t[i];t[i]:=t[j];t[j]:=a; 42 a:=x[i];x[i]:=x[j];x[j]:=a; 43 a:=y[i];y[i]:=y[j];y[j]:=a; 44 inc(i);dec(j); 45 end; 46 until i>j; 47 if i<r then kp(i,r); 48 if l<j then kp(l,j); 49 end; 50 begin 51 read(n,m); 52 for i:=1 to n do pre[i]:=i; 53 for i:=1 to m do 54 read(x[i],y[i],t[i]); 55 kp(1,m); 56 for i:=1 to m do 57 begin 58 if not judge(x[i],y[i]) then 59 begin 60 maxans:=max(t[i],maxans); 61 join(x[i],y[i]); 62 end 63 else continue; 64 end; 65 for i:=1 to n do 66 for j:=1 to n do 67 begin 68 if i=j then continue; 69 if not judge(i,j) then begin writeln(‘-1‘);halt;end; 70 end; 71 writeln(maxans); 72 end.
这道题基本上可以说是并查集的模板吧
[CodeVS]1638 修复公路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。