题解 | 修复公路

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int M=1e5+5;
int f[N];

struct node{
    int x,y,w;
}a[M];

int find(int x){
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
}

bool cmp(node &a ,node & b){
    return a.w<b.w;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].x>>a[i].y>>a[i].w;
    }
    for(int i=1;i<=n;i++){
        f[i]=i;
    }

    sort(a,a+m,cmp);
    int t=0;
    int cnt=0;
    for(int i=0;i<m;i++){
        int u=find(a[i].x);
        int v=find(a[i].y);
        if(u!=v){
            f[u]=v;
            t=max(t,a[i].w);
            cnt++;
        }
        if(cnt==n-1){
            cout<<t;
            return 0;
        }
    }
    cout<<-1;
}

Kruskal算法求解最小生成树的经典板子

核心：并查集维护数据，Kruskal算法求解最小生成树；

最短时间，又是城市间有边，很明显是图，有权重，就用Kruskal，自然就要用到并查集。注意的是这里的公路是同时开修的，所以在合并一次集合的时候，求取的是当下时间和权重最大的那个值，而不是累加。最后当合并了n-1次后，代表可以构成联通，否则就不可能。