题解

PS：本题在洛谷上有原题，难度为黄。

你说得对，但是本人这个蒟蒻自己独立做肯定是做不出来的。所以参考了这篇题解。不过只是借鉴了大概思路而已、
在洛谷上调了半天，发现数组开小了，我直接

---

题目大意：

现在给你 $N$ 个村庄与 $M$ 条路，道路是双向的。接下来 $M$ 行告诉你这条路所链接的村庄与修复这条公路的时间。请你输出把所有路都修好的时间。

思路：

类似最小生成树的 Kruskal 算法（似乎就是？）。先按时间进行排序，之后，如果两条路没有联通，则修理这一条路（等同于并查集的合并）。并把数量减一。合并完之后输出时间即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int fa[N],h[N];
int n,m;
struct node{
    int x,y,t;
}sz[N];
bool cmp(node a,node b){
    return a.t<b.t;
}
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    if(h[y]<h[x])swap(x,y);
    if(h[x]==h[y])h[y]=h[x]+1;
    fa[y]=x;
}
void init(){
    for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
}
int read(){
    int x=0,f=1;
    int ch=getchar();
    while(ch<'0' or ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0' and ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }return x*f;
}
void write(int x){
    if(x==0){
        putchar('0');
        return ;
    }
    if(x<0){
        putchar('-');
        x=-x;
    }if(x>9)write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read(),m=read();
    init();
    int cnt=n;
    for(int i=1;i<=m;i++)sz[i].x=read(),sz[i].y=read(),sz[i].t=read();
    sort(sz+1,sz+m+1,cmp);
    for(int i=1;i<=m;i++){
        int x=find(sz[i].x),y=find(sz[i].y);
        if(x!=y){
            merge(x,y),cnt--;
        }
        if(cnt==1){
            write(sz[i].t);
            return 0;
        }
    }if(cnt!=1)write(-1);
    return 0;
}

这个代码在最坏情况下时间复杂度为 $O(n + m \log{m} + m α(n))$