题解 | 继续畅通工程

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

const int N = 110;
int n,m,p[N];

struct edge{
    int a,b,w;
};

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

bool cmp(edge a,edge b){ //按照w升序排序
    return a.w<b.w;
}

int main() {
    while (cin >> n) { 
        if(n==0)break;
        m=n*(n-1)/2;
        edge edges[m];
        for(int i=0;i<m;i++){
            int a,b,w,flag;
            cin>>a>>b>>w>>flag;
            if(flag==0) edges[i]={a,b,w};
            else edges[i]={a,b,0};
        }

        //初始化并查集每个节点 1~n 
        for(int i=1;i<=n;i++) p[i]=i; 

        //把边升序排序
        sort(edges, edges+m,cmp);

        //Kruskal算法
        int res = 0,cnt=0;
        for(int i=0;i<m;i++){
            edge e = edges[i];
            int p1 = find(e.a);
            int p2 = find(e.b);
            if(p1!=p2){
                res+=e.w;
                cnt++;
                p[p1]=p2;
            }
        }
        if(cnt<n-1) ;
        else cout<<res<<endl;

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

【算法思路】：

1. 并查集+Kruskal最小生成树算法；
2. 若路已经修好，则就把他的权值设为0；