题解 | #[SCOI2005]繁忙的都市#

思路

最小生成树的板子题，前置知识：并查集以及Kruskal算法；
答案要求输出最小生成树的边数（那肯定是n-1啊）以及最大权值的边（那肯定是最后连的那一条啊）
因为做过最小生成树的课件，代码注释解释了很多，大家可以看看。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=300,maxm=20005;

struct E{
    int from,to,dis,next;
    bool operator <(const E b)const{ //用于排序边 
        return dis<b.dis;
    }
}e[maxm];

int n,m,u,v,c,num,mx,fa[maxn]; //mx存放第二个答案 
int cnt=0,head[maxn];

void addedge(int from,int to,int dis){ //链式前向星建边 
    e[++cnt].from=from;
    e[cnt].to=to;
    e[cnt].dis=dis;
    e[cnt].next=head[from];
    head[from]=cnt;
}

int find(int x){ //带路径压缩的查找操作 
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

void unite(int a,int b){ //合并两个集合 
    fa[find(a)]=find(b);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>c;
        addedge(u,v,c); //双向连边 
        addedge(v,u,c);
    }
    sort(e+1,e+1+cnt); //按边权从小到大排序 
    for(int i=1;i<=cnt;i++){
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){ //Kruskal算法，找到未合并的两点合并 
            unite(u,v);
            mx=e[i].dis; //更新最大边 
            //num++; 
        }
        //if(num==n-1) break; 可以在连了n-1条边时即使跳出 
    }
    cout<<n-1<<" "<<mx<<endl;
    return 0;
}