题解 | #继续畅通工程#

另一种更简便的方法是 可以 直接把权值设成0，这样他们就一定会优先级最高。

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

//例题11.4
const int maxn=110;
int father[maxn];
int height[maxn];

//初始化
void initial(){
    for(int i=0;i<maxn;i++){
        father[i]=-1;
        height[i]=0;
    }
}

//Find
int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}
//union
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if (fx==fy)return;
    if(height[fx]>height[fy]){
        father[fy]=fx;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
    }
    else{
        father[fx]=fy;
        height[fy]++;
    }
}

struct edge{
    int node1;
    int node2;
    int dist;
};

edge graph[maxn*maxn];

int compare(edge x,edge y){
    return x.dist<y.dist;
}

int kruskal(int edgenumber){
    int sum=0;
    for(int i=0;i<edgenumber;i++){
        edge e=graph[i];
        if (Find(e.node1)!=Find(e.node2)){
            Union(e.node1,e.node2);
            sum+=e.dist;
        }
    }
    return sum;
}

int main(){
    int n;
    while(cin>>n){
        initial();
        if(n==0)break;
        int edgenumber=n*(n-1)/2;
        int p1,p2,p3,p4;
        int zeros=0;
        for(int i=0;i<edgenumber;i++){
            cin>>p1>>p2>>p3>>p4;
            if(p4==1){
                Union(p1,p2);
            }
            else{
              graph[zeros].node1=p1;
              graph[zeros].node2=p2;
              graph[zeros].dist=p3;
              zeros++;
            }
        }
        sort(graph,graph+zeros,compare);
        int sum=kruskal(zeros);
        cout<<sum<<endl;
    }
    return 0;
}