题解 | #继续畅通工程#

#include<bits/stdc++.h>
using namespace std;
int N, a, b, Cost, state, edge_num;
struct edge {
    int one_pos;
    int another_pos;
    int cost;
};
edge e;
int root[101];
vector<edge> edges;//边的集合
//克鲁斯卡尔算法
int Kruskal() {
    int min_cost = 0;//最少花费
    //初始化：每一个顶点(村庄)都是一棵树，一共n棵树
    for (int i = 1; i <= N; i++) {
        root[i] = i; //自己的根是自己
    }
    for (int i = 0; i < edge_num; i++)
    {
        //如果不是一个集合，那么将两个集合(树)合并，并且将这条边的花费加入最小生成树的花费
        if (root[edges[i].one_pos] != root[edges[i].another_pos])
        {
            if (root[edges[i].one_pos] < root[edges[i].another_pos])
            {
                int small = root[edges[i].one_pos];
                int big = root[edges[i].another_pos];
                for (int k = 1; k <= N; k++)
                {
                    if (root[k] ==big)
                    {
                        root[k] = small;
                    }
                }
            }
            else
            {
                int big = root[edges[i].one_pos];
                int small = root[edges[i].another_pos];
                for (int k = 1; k <= N; k++)
                {
                    if (root[k] == big)
                    {
                        root[k] =small;
                    }
                }
            }
            min_cost += edges[i].cost;//将这条边的花费加入最小生成树的花费
        }
        //看看是不是所有村庄都汇集成了一棵大树
        bool flag = 1;//假设汇集成了
        for (int c = 1; c <= N; c++)
        {
            if (root[c] != 1)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1) break;
    }
    return min_cost;
}
int main() {
    while (cin >> N && N) {
        edges.clear();//清理上一轮的
        edge_num = (N - 1) * N / 2; //无向图的边的数目
        for (int i = 0; i < edge_num; i++) {
            cin >> a >> b >> Cost >> state;
            e.one_pos = a;
            e.another_pos = b;
            e.cost = Cost;
            if (state == 1) e.cost = 0;
            edges.push_back(e);//装入边集合
        }
        //将边按照cost排序
        sort(edges.begin(), edges.end(), [](const edge& a, const edge& b) {
            return a.cost < b.cost;
            });
        //克鲁斯卡尔算法
        cout << Kruskal() << endl;
    }

}
// 64 位输出请用 printf("%lld")