北大ACM2395——Out of Hay~最小生成树

北大ACM2395——Out of Hay~~最小生成树

题目求解的是最小生成树中的最大边：

一次AC代码：

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

class data
{
public:
	int from, to, cost;
};
data Edge[10005];

int par[2005];
int N, M, num;

int cmp(const data& a, const data& b)   //从小到大排序
{
	return a.cost < b.cost;
}
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 <= N; i++)
		par[i] = i;
	sort(Edge, Edge + num, cmp);        //排序
	for(i = 0; i < num; i++)
	{
		data e = Edge[i];
		if(finds(e.from) != finds(e.to)) //判断是否属于一个并查集
		{
			join(e.from, e.to);
			if(ans < e.cost)
				ans = e.cost;
		}
	}
	return ans;
}
int main()
{
	int a, b, c;
	while(scanf("%d%d", &N, &M) != EOF)
	{
		num = 0;
		for(int i = 0; i < M; i++)
		{
			scanf("%d%d%d", &a, &b, &c);
			Edge[num].from = a;
			Edge[num].to = b;
			Edge[num++].cost = c;
		}
		int ans = Kruskal();
		printf("%d\n", ans);
	}
	return 0;
}