并查集+Kruskal算法求解最小生成树
继续畅通工程
http://www.nowcoder.com/questionTerminal/16212f7d46e44174b5505997ea998538
跟前几道畅通工程的题一样，都是用Kruskal算法求最小生成树，唯一的区别是要处理已经修建好的道路 ，我的方法是如果检测到一个道路已经建好，就将他的花费置为0。然后就是常规并查集+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;
} 
投递用友等公司10个岗位
