P1111 修复公路
题目背景
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入输出格式
输入格式：
第1行两个正整数N，M
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。
输出格式：
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入样例#1：
4 4
1 2 6
1 3 4
1 4 5
4 2 3输出样例#1：
5说明
N<=1000，M<=100000
x<=N，y<=N，t<=100000
裸的克鲁斯卡尔啊。。
直接套板子就可以，什么都不用改
至于村子的连通性
我们可以把每个村子都看做一个点
能完全连接n个点的边数就是n-1
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int MAXN=1001;
8 void read(int & n)
9 {
10 char c='+';int x=0;
11 while(c<'0'||c>'9')c=getchar();
12 while(c>='0'&&c<='9')
13 {
14 x=x*10+c-48;
15 c=getchar();
16 }
17 n=x;
18 }
19 int n,m;
20 struct node
21 {
22 int u,v,w;
23 }edge[MAXN*100];
24 int comp(const node & a,const node & b)
25 {return a.w<b.w;}
26 int fa[MAXN];
27 int find(int x)
28 {
29 if(fa[x]==x)
30 return fa[x];
31 else
32 return fa[x]=find(fa[x]);
33 }
34 void unionn(int x,int y)
35 {
36 int fx=find(x);
37 int fy=find(y);
38 fa[fx]=fy;
39 }
40 int main()
41 {
42 read(n);read(m);
43 for(int i=1;i<=n;i++)
44 fa[i]=i;
45 for(int i=1;i<=m;i++)
46 {
47 read(edge[i].u);
48 read(edge[i].v);
49 read(edge[i].w);
50 }
51 int tot=0;
52 int ans=-1;
53 sort(edge+1,edge+m+1,comp);
54 for(int i=1;i<=m;i++)
55 {
56 if(find(edge[i].u)!=find(edge[i].v))
57 {
58 unionn(edge[i].u,edge[i].v);
59 tot++;
60 ans=max(ans,edge[i].w);
61 }
62 if(tot==n-1)
63 break;
64 }
65 if(tot!=n-1)
66 printf("-1");
67 else
68 printf("%d",ans);
69 return 0;
70 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-06-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录