题解 | #还是畅通工程#

最主要的还是并查集的使用。kruskal算法只不过是在和并集合的时候添加了条件。

#include <bits/stdc++.h>

using namespace std;

//定义的边
struct Edge {
    int a;
    int b;
    int weight;

    Edge(int _a, int _b, int _weight) {
        a = _a;
        b = _b;
        weight = _weight;
    }
};

int father[1010];

//初始化
void InitDisjointSet(int n) {
    //0~n-1
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

//找爸爸
int FindDisjointset(int u) {
    if (u == father[u]) {
        return u;
    } else {
        father[u] = FindDisjointset(father[u]);
        return father[u];
    }
}

//合并
void UnionDisjointSet(int u, int v) {
    int uroot = FindDisjointset(u);
    int vroot = FindDisjointset(v);
    father[vroot] = uroot;
}


//将边按权值从小到大排列
bool compare(Edge lhs, Edge rhs) {
    /* sort是基于快速排序实现的，基于比较的排序。默认<。
     * 重点编程：设计“compare”函数。返回值：bool；函数名：无所谓；两个参数：类型和容器元素一致。
     * 当左边和右边不会发生交换时，返回真；发生交换时，返回假。*/
    return lhs.weight < rhs.weight;
}

//kruskal算法的实现
int Kruskal(int n, vector<Edge> &edgeVec) {
    sort(edgeVec.begin(), edgeVec.end(), compare);//将边按权值从小到大排列
    //遍历edgeVec加入子图
    int totalWeight = 0;//总权值
    int curEdgeNum = 0;//目前的边数
    for (int i = 0; i < edgeVec.size(); ++i) {
        int u = edgeVec[i].a;
        int v = edgeVec[i].b;
        int weight = edgeVec[i].weight;
        if (FindDisjointset(u) != FindDisjointset(v)) {//还未加入集合。（不属于同一个集合）
		  //最主要的还是并查集的使用。kruskal算法只不过是在和并集合的时候添加了条件。
            UnionDisjointSet(u, v);//加入边集
            ++curEdgeNum;
            totalWeight += weight;

            if (curEdgeNum == n - 1) {//达到最大边数
                //最小生成树用贪心算法恰好能得到最优解，但是不好证明。
                break;
            }
        }
    }
    return totalWeight;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (0 == n) {
            break;
        }
        vector<Edge> edgeVec;//存储所有的边
        InitDisjointSet(n + 1);//初始化并查集
        for (int i = 0; i < (n - 1) * n / 2; ++i) {//输入数据
            int u, v, weight;
            scanf("%d%d%d", &u, &v, &weight);
            Edge e(u, v, weight);
            edgeVec.push_back(e);
        }
        //kruskal
        printf("%d\n", Kruskal(n, edgeVec));
    }
    return 0;
}