并查集+Kruskal算法求解最小生成树

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

using namespace std;

const int MAXN = 110;
int father[MAXN];
int height[MAXN];
struct Edge{
	int from;
	int to;
	int length;
	int tag;
}; 
Edge edge[5000];
void Initial(int 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);
	y = Find(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]++;  
		}
	}
	return;
}
bool Compare(Edge x, Edge y)
{
	return x.length < y.length;
}
int Kruskal(int n, int edgelength)//Kruskal算法求最小生成树
{
	Initial(n);
	int cost = 0;
	for(int  i  = 0; i < edgelength; i++)
	{
		int x = edge[i].from;
		int y  = edge[i].to;
		if(Find(x) != Find(y))
		{
			Union(x, y);
			cost += edge[i].length;
		} 
	}
	return cost;
}
int main()
{
	int n;
	while(scanf("%d", &n) != EOF)//顶点数
	{
		if(n == 0)
			break;
		int edgelength = n *  (n - 1) / 2;//边数
		for(int i = 0;  i < edgelength; i++)
		{
			scanf("%d%d%d%d", &edge[i].from, &edge[i].to, &edge[i].length, &edge[i].tag);
			if(edge[i].tag == 1)//如果道路已建，花费置为0
			{
				edge[i].length = 0;
			}
		 } 
		 sort(edge, edge + edgelength, Compare);//将边集按权值从小到大排序
		 int cost = Kruskal(n, edgelength);//通过Kruskal算法求得最小生成树权值之和即为结果
		 printf("%d\n", cost);
	}
	return 0;
}