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

思路：
1.先存储所有的边，包括起点，终点，权值u,v,w
2.对所有的边按权值从小到大排序
3.最小生成树得到的边数一定是n-1（点的数目减一），按权值从小到大取边，如果选中该边，就把这条边的两个点加入到一个集合（表示有同样的归属关系，就是我们所说的并查集）里面，下次选边时，如果有节点已经在这个集合中，说明会构成回路，不满足最小生成树的性质，就要抛弃这条边。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int ,int> pii;
const int inf = 0x3f3f3f3f;
const int N = 2e5+5;
int n,m,cnt,ans,f[N];

struct edge
{
    int u,v,w;
}e[200005];
int find(int x)
{
    return f[x]==x ? x: (f[x] = find(f[x]));
}
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
void kruskal()
{
    for(int i=1;i<=n;i++) f[i] = i;
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        int a = find(e[i].u);
        int b = find(e[i].v);
        if(a==b) continue;
        ++cnt;
        f[b] = a;
        if(cnt==n-1) 
        {
            ans = e[i].w;
            break;
        }
    }
    cout<<cnt<<" "<<ans<<'\n';
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[i].u = a,e[i].v = b,e[i].w = c;
    }
    kruskal();
    return 0;
}

我的博客：
https://blog.csdn.net/qq_50285142/article/details/116927656