题解 | #用kruskal算法解决#

//采用kruskal算法，所以边要按权值从小到大排列，可采用优先队列处理。已加入的结点不能再加，采用并查集处理
#include "stdio.h"
#include "queue"
#define N 1000
using namespace std;
int father[N];
int height[N];
int n;
struct Edge{
    int x;//起点
    int y;//终点
    int weight;//权重
};
bool operator < (Edge lhs,Edge rhs){
    if (lhs.weight > rhs.weight)
        return true;
    else
        return false;
}
void init(int n){//并查集的初始化
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        height[i] = 1;
    }
}

int find(int x){//查找祖先根节点
    if (x != father[x]){
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x,int y){//并查集的合并
    x = father[x];
    y = father[y];
    if (height[x] > height[y]){
        father[y] = x;
    } else if (height[x] < height[y]){
        father[x] = y;
    } else{
        father[x] = y;
        ++height[y];
    }
}
int main(){
    int x,y,weight;
    priority_queue<Edge> myPQueue;
    while (scanf("%d",&n)!=EOF){
        if(n == 0)
            break;
        for (int i = 0; i < n*(n-1)/2; ++i) {
            Edge edge;
            scanf("%d%d%d",&x,&y,&weight);
            edge.x = x;edge.y = y;edge.weight = weight;
            myPQueue.push(edge);
        }
        init(n);int sum = 0;
        while (!myPQueue.empty()){
            Edge edge = myPQueue.top();
            myPQueue.pop();
            //看edge(x,y)是否在同一个并查集中
            //若不在同一个则Union(同时加上权值)，否在同一个则continue
            if (find(edge.x) == find(edge.y)){//x与y在同一个并查集中
                continue;
            } else{
                Union(edge.x,edge.y);
                sum += edge.weight;
            }
        }
        printf("%d\n",sum);
    }
}