POJ 2395 Out of Hay题解 《挑战程序设计竞赛》

POJ 2395 Out of Hay

求干草：奶牛没草吃了，要去附近的农场找，求最短遍历路径上最长的那条路。

2.5 它们其实都是“图”

最小生成树

水题一道，作为2.5节最后一题真是抬举它了。唉，每天学点NLP的东西就不知不觉这个点了，这才想起还有N1和托福要背，时间不够用呀。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_E 10000 + 16

// 并查集相关数据与算法
#define MAX_N 2000 + 16
int parent[MAX_N];
int height[MAX_N];

void init(const int& n)
{
	for (int i = 0; i < n; ++i)
	{
		parent[i] = i;
		height[i] = 0;
	}
}

int find(const int& x)
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		return parent[x] = find(parent[x]);
	}
}

void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y)
	{
		return;
	}

	if (height[x] < height[y])
	{
		parent[x] = y;
	}
	else
	{
		parent[y] = x;
		if (height[x] == height[y])
		{
			++height[x];
		}
	}
}

bool same(const int& x, const int& y)
{
	return find(x) == find(y);
}
// End Of 并查集

struct edge
{
	int u, v, cost;
	edge(int u = 0, int v = 0, int cost = 0) : u(u), v(v), cost(cost) {}
	bool operator < (const edge & e2) const
	{
		return cost < e2.cost;
	}
};
edge es[MAX_E];
int V, E;
int kruskal()
{
	sort(es, es + E);	// 按照权值从小到大排序
	init(V);
	int res = 0;
	for (int i = 0; i < E; ++i)
	{
		edge e = es[i];
		if (!same(e.u, e.v))
		{
			unite(e.u, e.v);
			res = max(res, e.cost);
		}
	}

	return res;
}


///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> V >> E;
	for (int i = 0; i < E; ++i)
	{
		cin >> es[i].u >> es[i].v >> es[i].cost;
		--es[i].u; --es[i].v;
	}
	cout << kruskal() << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2395 Out of Hay题解 《挑战程序设计竞赛》