记录编号	305714	评测结果	AAAAAAAAAAA
题目名称	[POJ2395] Out of Hay	最终得分	100
用户昵称	SPA	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2016-09-11 06:21:10	内存使用	0.43 MiB

#include "stdio.h"
#include "algorithm"
using namespace std;

template <class T> inline void Read(T& x) {
	x = 0; char ch; short minus = 1;
	while (ch = getchar(), ch<'-' || ch>'9');
	if (ch == '-') minus = -1, ch = getchar();
	while (x = x * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	x *= minus;
}

const size_t maxn = 2000 + 10, maxm = 10000 + 10;

int n, m;
struct Edge {
	int from, to, dis;
	inline bool operator <(Edge b) const { return dis < b.dis; }
} E[maxm << 1];
int tot = 0;
int fa[maxn] = {0};

inline void AddEdge(int from, int to, int dis) {
	E[++tot].from = from; E[tot].to = to; E[tot].dis = dis;
}

int GetFa(int x) {
	return fa[x] == x ? x : fa[x] = GetFa(fa[x]);
}

inline void Kruskal(int &ans) {	
	sort(E + 1, E + tot + 1);
	for (int i = 1; i <= n; ++i) fa[i] = i;
	int cnt = n;
	for (int i = 1; i <= tot; ++i) {
		int f1 = GetFa(E[i].from), f2 = GetFa(E[i].to);
		if (f1 != f2) {
			fa[f1] = f2;
			ans = max(ans, E[i].dis);
			--cnt;
			if (cnt == 1) break;
		}
	}
	if (cnt != 1) ans = -1;
}

#define SUBMIT

int main() {
#ifdef SUBMIT
	freopen("outofhay.in", "r", stdin);
	freopen("outofhay.out", "w", stdout);
#endif

	Read(n); Read(m);
	int u, v, w;
	for (int i = 1; i <= m; ++i) {
		Read(u); Read(v); Read(w);
		AddEdge(u, v, w); AddEdge(v, u, w);
	}
	int ans = 0;
	Kruskal(ans);
	printf("%d\n", ans);

#ifndef SUBMIT
	puts("\n--------------------");
	getchar(), getchar();
#else
	fclose(stdin); fclose(stdout);
#endif
	return 0;
}