首页 > 代码库 > P1111 修复公路
P1111 修复公路
P1111 修复公路
题目背景
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入输出格式
输入格式：
第1行两个正整数N，M
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。
输出格式：
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入样例#1：
4 41 2 61 3 41 4 54 2 3
输出样例#1：
5
说明
N<=1000，M<=100000
x<=N，y<=N，t<=100000
最小生成树模板题
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 struct edge{ 8 int a,b,c; 9 }e[200100];10 int n,m;11 int far[5100];12 int ans,cnt;13 14 int find(int a)15 {16 return far[a]==a?a:far[a]=find(far[a]);17 }18 bool cmp(edge a,edge b)19 {20 return a.c<b.c;21 }22 23 int main()24 {25 scanf("%d%d",&n,&m);26 for(int i=1;i<=n;++i) far[i] = i;27 for(int i=1;i<=m;++i)28 {29 int a,b,c;30 scanf("%d%d%d",&a,&b,&c);31 e[i].a=a;32 e[i].b=b;33 e[i].c=c;34 }35 sort(e+1,e+m+1,cmp);36 for(int i=1;i<=m;++i)37 {38 int aa = find(e[i].a);39 int bb = find(e[i].b);40 if(aa!=bb)41 {42 cnt++;43 far[aa] = far[bb];44 ans = max(ans,e[i].c);45 if(cnt==(n-1))break;46 }47 }48 if(cnt==(n-1)) cout<<ans;49 else cout<<"-1";50 return 0;51 }
P1111 修复公路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。