道路建设 （kruskal算法）

题目链接：https://ac.nowcoder.com/acm/problem/15108
显然这是一道 最小生成树的题
其中利用的是 kruskal算法
kruskal 算法思想：贪心选取最短的边来组成一棵最小的生成树。
具体做法：先将所有的边做排序，然后利用并查集作判断来优先选择较小的边，直 到建成一棵生成树。
实现方式：并查集
模板代码：

下面贴上本题代码：

#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<cstring>
using namespace std;
int c, n, m;
struct road
{
    int u, v, h;
}edge[10005];
int fa[105];
int find(int x) {
    return (fa[x] == x ? x : find(fa[x]));
}
void merge(int x, int y) {
    fa[find(x)] =find( y);
}
bool cmp(road a, road b) {
    return (a.h < b.h);
}
void Kruskal() {
    int cnt = 0,sum=0;//cnt：造的路的条数 sum：造的路的总价值
    sort(edge + 1, edge + n + 1, cmp);
    for (int i = 1;i <= m;i++) { fa[i] = i; }
    for (int i = 1;i <= n;i++) {
        int u = edge[i].u, v = edge[i].v;
        if (find(u) != find(v)) {
            merge(u, v);
            cnt++;
            sum += edge[i].h;
            if (cnt >= n - 1) { break; }
        }
    }
    if (cnt<m-1 || sum>c) { cout << "No\n"; }//m个城市连通，至少需要m-1条道路
    else {
        cout << "Yes\n";
    }
}
int main(){
    cin >> c>>n >> m;
    for (int i = 1;i <= n;i++) { cin >> edge[i].u >> edge[i].v >> edge[i].h; }
    Kruskal();
}

谢谢浏览哈