P1111 修复公路

XichenOC · 2024-10-18 13:49:02 · 题解

P1111 修复公路

思路：

本题我们可以运用贪心的思想，将修剪每条路的时间从小到大进行排序，然和用并查集来依次加入道路所连接的两个村庄。若两个村庄已经在同一个集合里，代表这两个村庄联通。我们只需要找到连接村庄的道路的最大修建时间，输出即可。但要在输出前遍历每个点，看它们是否在一个集合里。不在就输出-1；

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
struct edge{
    int u,v,w;
    bool operator<(const edge &a)const{return w<a.w;}
}a[N];
int fa[N];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    sort(a+1,a+1+m);
    int ans=0;
    for(int i=1;i<=m;i++){
        if(find(a[i].u)!=find(a[i].v)){
            ans=max(ans,a[i].w);
            merge(a[i].u,a[i].v);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i)res++;
        if(res>1){
            cout<<-1;
            return 0;
        }
    }
    cout<<ans;
}

并查集讲解