题目描述 给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路） 输入输出格式 输入格式： 第111行两个正整数N,M 下面M行，每行3个正整数x,y,t，告诉你这条公路连着x,两个村庄，在时间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
解释：最小生成树裸题.记录最大边就好了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1004 using namespace std; struct node{ int a,b,c; }; node e[100002]; int father[N]={0}; void init(){ for(int i=0;i<N;i++) father[i]=i; } int find(int x){ if(x==father[x]) return x; return father[x]=find(father[x]); } void merge(int x,int y){ x=find(x);y=find(y); father[x]=y; } bool same(int x,int y){ return find(x)==find(y); } int n=0,m=0; bool cmp(node a,node b){ return a.c<b.c; } int main(){ ios::sync_with_stdio(false); init(); cin>>n>>m; for(int i=1;i<=m;i++) cin>>e[i].a>>e[i].b>>e[i].c; sort(e+1,e+1+m,cmp); int ret=-1; int num=0; for(int i=1;i<=m;i++){ if(!same(e[i].a,e[i].b)){ num++; merge(e[i].a,e[i].b); ret=max(ret,e[i].c); } } if(num<n-1) cout<<-1<<endl; else cout<<ret<<endl; return 0; }