POJ 2395 Out of Way

想法：
    這題與POJ 1861一模一樣，求最小生成樹的最大邊長而已。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	struct Edge{
	int A;
	int B;
	int Len;
	}E[15001];
	int Set[2001];
	bool cmp(const Edge &A, const Edge &B);
	void Set_Initial(const int &N);
	int Find_Root(const int &x);
	bool Union(const Edge &E);
	int main()
	{
	int N, M, A, B, L;
	while (scanf("%d %d", &N, &M) == 2) {
	for (int i = 0; i < M; ++i)
	scanf("%d %d %d", &E[i].A, &E[i].B, &E[i].Len);
	sort(E, E + M, cmp);
	Set_Initial(N);
	vector<Edge> Ans;
	for (int i = 0, currentEdge = 0; currentEdge != N - 1; ++i)
	if (Union(E[i])){
	++currentEdge;
	Ans.push_back(E[i]);
	}
	printf("%d\n", (Ans.end()-1)->Len);
	}
	}
	bool cmp(const Edge &A, const Edge &B) {
	return A.Len < B.Len;
	}
	void Set_Initial(const int &N)
	{
	for (int i = 1; i <= N; ++i)
	Set[i] = i;
	}
	int Find_Root(const int &x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = Find_Root(Set[x]);
	}
	bool Union(const Edge &E)
	{
	int x = Find_Root(E.A);
	int y = Find_Root(E.B);
	if (x != y) {
	Set[x] = y;
	return true;
	}
	return false;
	}

view raw [POJ] 2395 Out of Way.cpp hosted with ❤ by GitHub