P1111 修复公路

点击查看代码

#include<bits/stdc++.h>
using namespace std;

const int N=1010,M=1e5+10;

struct Edge{
    int a,b,w;
    bool operator< (const Edge &W) const {
        return w<W.w;
    }
}edges[M];
int n,m;
int p[N];
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges+1,edges+1+m);

    for(int i=1;i<=n;i++) p[i]=i;
    int res=0,cnt=0;
    for(int i=1;i<=m;i++){
        int a,b,w;
        a=find(edges[i].a),b=find(edges[i].b),w=edges[i].w;
        if(a!=b){
            p[a]=b;
            res=w;
            cnt++;
        }
    }

    if(cnt<n-1) return -1;
    else return res;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;

    for(int i=1;i<=m;i++){
        cin>>edges[i].a>>edges[i].b>>edges[i].w;
    }

    cout<<kruskal()<<"\n";

    return 0;
}