北大ACM1258——Agri-Net~~最小生成树

浏览数：43 / 时间：2015年06月09日

比较简单的题目.

直接附AC的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

class data
{
public:
	int form, to, height;
};
data Edge[10005];
int N, num, par[105];

int cmp(const data& a, const data& b)    //从小到大排序
{
	return a.height < b.height;
}

int finds(int x)                        //并查集查找函数
{
	if(x == par[x])
		return x;
	else
		return par[x] = finds(par[x]);
}

void join(int x, int y)                 //并查集合并函数
{
	x = finds(x);
	y = finds(y);
	if(x != y)
		par[y] = x;
}

int Kruskal()                          //最小生成树算法Kruskal
{
	int i, ans = 0;
	for(i = 0; i < 105; i++)
		par[i] = i;
	sort(Edge, Edge + num, cmp);
	for(i = 0; i < num; i++)
	{
		data e = Edge[i];
		if(finds(e.form) != finds(e.to)) //判是否属于同一个并查集，避免形成环
		{
			join(e.form, e.to);
			ans += e.height;
		}
	}
	return ans;
}

int main()
{
	int i, j, cost;
	while(scanf("%d", &N) != EOF)
	{
		num = 0;
		for(i = 1; i <= N; i++)
			for(j = 1; j <= N; j++)
			{
				scanf("%d", &cost);
				if(i != j)
				{
					Edge[num].form = i;
					Edge[num].to = j;
					Edge[num++].height = cost;
				}
			}
		int ans = Kruskal();
		printf("%d\n", ans);
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

北大ACM1258——Agri-Net~~最小生成树