题解 | 继续畅通工程

#include <iostream>
#include <algorithm>
using namespace std;

int village[101];

typedef struct Edge{
    int a, b;
    int cost;
    int status;
} Edge;
Edge edge[5000];

bool cmp(Edge a, Edge b){
    if(a.status != b.status) return a.status > b.status; // 已修的边，先于未修的边
    return a.cost < b.cost; // 成本低的先于成本搞得
}

// 判断是否联通
bool isSameSet(){
    int res=0;
    for(int i=1; i<=village[0]; i++){
        if(village[i] == -1) res++;
        if(res > 1) return false;
    }
    return true;
}

// 寻找当前节点的根节点
int findRoot(int a){
    if(village[a] == -1) return a;      // 判断是否为根节点
    int tmp = findRoot(village[a]);     // 递归查找父节点的根节点
    village[a] = tmp;                   // 将当前节点的父节点直接设置为根节点，因为集合查找是否同属于一个集合的时候，是看根节点是否相同
    return tmp;
}

int main() {
    int n;
    while(cin>>n){
        if(n==0) break;
        // 初始化，每个节点单独一个集合
        for(int i=1; i<=n; i++){
            village[i] = -1;
        }
        village[0] = n; // 村落的个数
        int lines = n*(n-1)/2;
        for(int i=0; i<lines; i++){
            cin >> edge[i].a >> edge[i].b >> edge[i].cost >> edge[i].status;
        }
        // 排序
        sort(edge, edge+lines, cmp);
        // 计算
        int sum=0;
        int cur=0;
        // 判断是否联通，判断是否修完所有的路
        while(!isSameSet() && cur < lines){
            int a_root = findRoot(edge[cur].a);
            int b_root = findRoot(edge[cur].b);
            // 如果两者根节点不相同，证明不在同一集合，不连通
            if(a_root != b_root){
                village[a_root] = b_root;
                // 如果还没修路，则增加花费
                if(edge[cur].status == 0) sum+=edge[cur].cost;
            }
            cur++;
        }
        cout << sum << endl;
    }
}