题目背景 AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述 给出A地区的村庄数NN，和公路数MM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入格式 第11行两个正整数N,MN,M
下面MM行，每行33个正整数x, y, tx,y,t，告诉你这条公路连着x,yx,y两个村庄，在时间t时能修复完成这条公路。
输出格式 如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1−1，否则输出最早什么时候任意两个村庄能够通车。
分析：这道题没想到的就是sum==n-1来判断是否可以联通。。。 还没太想明白。。。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn=1005; int n,m,i,j,ans,sum,x,y; int f[maxn]; struct node { int x,y,t; }s[100005]; bool cmp(struct node a,struct node b) { return a.t<b.t; } void in_it() { for(int i=1;i<=n;i++) { f[i]=i; } } int find_set(int x) { if(x!=f[x]) f[x]=find_set(f[x]); return f[x]; } void union_set(int x,int y) { int tx=find_set(x); int ty=find_set(y); if(tx!=ty) f[tx]=ty; } int main() { while(~scanf("%d %d",&n,&m)) { ans=0; sum=0; in_it(); for(i=1;i<=m;i++) { scanf("%d %d %d",&s[i].x,&s[i].y,&s[i].t); } sort(s+1,s+1+m,cmp); for(i=1;i<=m;i++) { x=find_set(s[i].x); y=find_set(s[i].y); if(x==y) continue; f[x]=y; sum++; ans=max(ans,s[i].t); } if(sum!=n-1) printf("-1\n"); else printf("%d\n",ans); } return 0; }