题解

这道题就是一个并查集+贪心，还算简单

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+5;
struct node{
int x,y,t;
}r[100005];
bool cmp(node a,node b){
    return a.t<b.t;
}
int f[N];//代表i的祖先
int find(int x){//找x的祖先 
	if(f[x]==x)return x;
	return f[x]=find(f[x]);//当前x的祖先
	//find(f[x])找x祖先的祖先 
} 
void unite(int x,int y){
	int rootx=find(x);//找x的祖先
	int rooty=find(y);//找y的祖先
	//如果x和y的祖先不同 就把y设为x祖先的祖先 
	if(rootx!=rooty)f[rootx]=rooty; 
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
    int ans=0,all=0;
    for(int i=1;i<=m;i++)
        cin>>r[i].x>>r[i].y>>r[i].t;
    sort(r+1,r+m+1,cmp);//贪心一下，先修时间最少的
    for(int i=1;i<=m;i++){
        int u=r[i].x，v=r[i].y，t=r[i].t;
        if(find(u)!=find(v)){//如果村子没有联通
            unite(u,v);
            all++;//记录修了几条路
            if(all==n-1){//如果修了n-1条路
                cout<<t;//路是同时修的，所以直接输出t
                return 0;
            }
        }
    }
    cout<<-1;
	return 0;
}