题意：

农场之间相互连接，要求输出最小连通中最长的那条边的权值

要点：

又是一道模板题，POJ上最小生成树咋这么多水题，要做点难的啊。

15347115

Accepted

292K

79MS

892B

2016-04-03 13:07:56

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 10005using namespace std;int p[maxn];int m, n;struct edge{	int u, v, len;}e[maxn];bool cmp(edge a, edge b){	return a.len < b.len;}void init(){	for (int i = 1; i <= m; i++)		p[i] = i;}int find(int x){	if (p[x] == x) return x;	return p[x] = find(p[x]);}bool merge(int x, int y){	x = find(x);	y = find(y);	if (x != y)	{		p[x] = y;		return true;	}	return false;}int kruskal(){	init();	sort(e, e + n, cmp);	int max = -1, edges = 0;	for (int i = 0; i < n; i++)	{		if (merge(e[i].u, e[i].v))		{			if (max < e[i].len)				max = e[i].len;			edges++;		}		if (edges + 1 == m)			return max;	}}int main(){	while (~scanf("%d%d", &m, &n))	{		for (int i = 0; i < n; i++)			scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].len);		printf("%d\n", kruskal());	}	return 0;}