题解 |和最小生成树思路一致，并查集实现Kruskal算法

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

#define maxnum 100
int tree[maxnum];
int height[maxnum];

struct edge{
    int from;
    int to;
    int weight;
}edges[maxnum*(maxnum-1)/2];

bool compare(edge x,edge y){
    return x.weight<y.weight;
}

void initial(int n){
    for(int i=1;i<=n;++i){
        tree[i]=i;
        height[i]=0;
    }
}

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

void Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(height[x]>height[y]){
        tree[y]=x;
    }
    else if(height[x]<height[y]){
        tree[x]=y;
    }
    else{
        tree[y]=x;
        height[x]++;
    }
}

int kruskal(int edgesize){
    sort(edges,edges+edgesize,compare);
    int res=0;
    for(int i=0;i<edgesize;++i){
        edge cur=edges[i];
        if(find(cur.from)!=find(cur.to)){
            res+=cur.weight;
            Union(cur.from,cur.to);
        }
    }
    return res;
}

int main() {
    int n;
    while(cin>>n){
        if(n==0) break;
        int edgesize=n*(n-1)/2;
        initial(n);
        for(int i=0;i<edgesize;++i){
            int m;
            cin>>edges[i].from>>edges[i].to>>edges[i].weight>>m;
            if(m==1) Union(edges[i].from,edges[i].to);
        }
        cout<<kruskal(edgesize)<<endl;
    } 
}
// 64 位输出请用 printf("%lld")