题解 | #继续畅通工程#注释版

。由于已经建好的路不一定是在最小生成树中，所以这个边数的约束没有必要，只要连通的条件达成就行。

#include <bits/stdc++.h>

using namespace std;

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

    Edge(int _a, int _b, int _weight, int _isBuilt) {
        a = _a;
        b = _b;
//        isBuilt = _isBuilt;
        if (_isBuilt == 1) {//如果已经建好了，这条路的权重就是零。只要加入并查集就好
            weight = 0;
        } else {
            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> &roads) {
    int roadCount = 0;
    int weighSum = 0;
    sort(roads.begin(), roads.end(), compare);
    for (int i = 0; i < roads.size() ; ++i) {
        int a = roads[i].a;
        int b = roads[i].b;
        int weight = roads[i].weight;
        if (FindDisjointset(a) != FindDisjointset(b)) {
            UnionDisjointSet(a, b);
            weighSum += weight;
            roadCount++;
//            由于已经建好的路不一定是在最小生成树中，所以这个边数的约束没有必要，只要上述连通的条件达成就行。
//            if (roadCount == N - 1) {//达到最大边数
//                break;
//            }
        }
    }
    return weighSum;
}


int main() {
    int N;
    while (scanf("%d", &N) != EOF) {
        if (0 == N) {
            return 0;
        }
	    //初始化
        vector<Edge> roads;
        InitDisjointSet(N + 1);
        int edgeNum = N * (N - 1) / 2;
	    //录入信息
        for (int i = 0; i < edgeNum; ++i) {
            int a;
            int b;
            int weight;
            int isBuilt;
            scanf("%d%d%d%d", &a, &b, &weight, &isBuilt);
            Edge r(a, b, weight, isBuilt);
            roads.push_back(r);
        }
        printf("%d\n", Kruskal(N, roads));
        roads.clear();
    }
    return 0;
}