题解 | #找出直系亲属#

kruskal解决最小生成树问题

#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){
    initial();
    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){
        if(n==0)break;
        int edgenumber=n*(n-1)/2;
        for(int i=0;i<edgenumber;i++)cin>>graph[i].node1>>graph[i].node2>>graph[i].dist;
        sort(graph,graph+edgenumber,compare);
        int sum=kruskal(edgenumber);
        cout<<sum<<endl;
    }
    return 0;
}