题解 | #还是畅通工程#

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std; 

const int MAXN = 1000;

struct Edge{    //定义边结构体
	int from;
	int to;
	int length;
};

Edge edge[MAXN * MAXN];   //边的数量是定点数量的平方

int father[MAXN];    //用以表示每个节点的父节点是什么样的

int height[MAXN];   

void Initial(int n){    //n个节点
	for(int i = 0; i < n; ++i){    //初始状态下，每个节点的父节点是其自身
		father[i] = i;
		height[i] = 0;
	}
	return;
}

int Find(int x){
	if(x != father[x]){  //表示当前节点不是根节点，需要继续向上查找
		father[x] = Find(father[x]);    //将路径压缩，可以提高查找效率
	}
	return father[x];
}

void Union(int x,int y){  //合并，将一棵树作为另一棵树的子树
	x = Find(x);   //找到x的根节点
	y = Find(y);    //找到y的根节点
	if(x != y){    //说明这两个节点本身不属于同一个集合，需合并
		if(height[x] < height[y]){   //将树高较高的作为树高较低的子树进行合并
			father[x] = y;    
		}else if(height[x] > height[y]){
			father[y] = x;    
		}else{   //高度相同时，可任意连接
			father[y] = x;   
			height[x]++;   //树的高度递增1
		}
	}
}

bool Compare(Edge x,Edge y){
	return x.length < y.length;
}

int Kruskal(int n,int edgeNum){
	Initial(n);   //先初始化
	sort(edge,edge + edgeNum,Compare);  //按照边的权值升序排序
	int sum = 0;   //统计路径之和
	for(int i = 0; i < edgeNum; ++i){
		Edge current = edge[i];
		if(Find(current.from) != Find(current.to)){   //两个定点不属于同一个集合，就进行合并
			Union(current.from,current.to);
			sum += current.length;
		}
	}
	return sum;
}



int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		if(n == 0){
			break;
		}
		int edgeNum = n * (n - 1) / 2;   //n个顶点，n * (n - 1) / 2条边
		for(int i = 0; i < edgeNum; ++i){    //输入边的信息
			scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].length);
		}
		int answer = Kruskal(n,edgeNum);
		printf("%d\n",answer);
	}
	return 0;
}