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

最小生成树版子题不多说，上代码

#include <bits/stdc++.h>
using namespace std;
const int N=305;	//题目数据范围
int f[N];	//father数组
int deep[N]; //并查集的优化，记录小挂大
int rfind(int x) {	//查询返回根节点的值，优化后回溯过程中会将节点直接挂在根节点下
    if (x==f[x])return x; //如果自己就是自己祖先，代表找到根节点，返回
    return f[x] = rfind(f[x]); //向上递归，找祖先
}
void merge(int x,int y) {	//合并函数
    if (rfind(x)==rfind(y))return;	//如果根节点相同代表已经在一个集合中
    x=rfind(x);	
    y=rfind(y); //二者都找寻自己的根节点
    if (deep[x]>deep[y]) f[y]=x;
    else if (deep[x]<deep[y]) f[x]=y;
    else f[x]=y,deep[y]++; //按照小挂大原则合并根节点，相同深度deep数组对应节点的值要+1
}
struct edge {
    int u;
    int v;
    int w;
    edge(int u,int v,int w) {
        this->u=u;
        this->v=v;
        this->w=w;
    }
};
int main() {
    int n,m;cin >> n >> m;
    vector<edge> edges;	//存储边的数组
    while (m--) {
        int u,v,w;cin >> u >> v >> w;
        edges.emplace_back(u,v,w);
    }
    sort(edges.begin(),edges.end(),[](auto a,auto b) {
        return a.w < b.w;
    }); 	//不需要建图，将边按权排序
    int sum=0;
    for (int i=1;i<=n;i++) {
        f[i]=i;
        deep[i]=1;
    }	//初始化
    for (auto e : edges) {	//从小到大遍历
        if (rfind(e.u) != rfind(e.v)) {
            merge(e.v,e.u);	//可以合并两个节点就合并
            sum = max(sum,e.w);
        }	//最终一定是一个最小生成树
    }
    cout << n-1 << " " << sum << endl;
}