学步园

来源：http://poj.org/problem?id=1861

题意：有一些公司，公司之间需要连接起来。给出了哪些公司可以连接以及连接边的长度。求最小生成树中最大的边，以及最小生成树的边数，以及输出一颗可行的最小生成树。

思路：基本上就是裸的kruskal了。可以水之。

代码：

#include <iostream>
#include <cstdio> 
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 1010, M = 15010;
struct edge{
	int x,y,value;
}ee[M];
struct solve{
	int lp,rp;
}ss[M];
int father[N],numedge,n,m,cnt,numsolve;
bool cmp(edge a,edge b){
	return a.value < b.value;
}
int find(int x){
	if(father[x] == x)
		return father[x];
	return find(father[x]);
}
bool Union_Set(int x,int y){
	int lp = find(x);
	int rp = find(y);
	if(lp == rp)
		return false;
	else{
	  father[lp] = rp;
	  return true;
	}
}
int kruskal(){
	cnt = 0;
	int mmax = 0;
	numsolve = 0;
	for(int i = 1; i <= n; ++i)
		father[i] = i;
	for(int i = 0; i < numedge; ++i){
	  int lx = ee[i].x;
	  int rx = ee[i].y;
	  if(Union_Set(lx,rx)){
	    cnt++;
		if(mmax < ee[i].value)
			mmax = ee[i].value;
		ss[numsolve].lp = lx;
		ss[numsolve].rp = rx;
		numsolve++;
	  }
	}
	return mmax;
}
int main(){
	while(scanf("%d%d",&n,&m) != EOF){
	  int x,y,z;
	  numedge = 0;
	  while(m--){
	    scanf("%d%d%d",&x,&y,&z);
		ee[numedge].x = x;
		ee[numedge].y = y;
		ee[numedge].value = z;
		numedge++;
	  }
	  sort(ee,ee+numedge,cmp);
	  int ans = kruskal();
	  printf("%d\n",ans);
	  printf("%d\n",cnt);
	  for(int i = 0; i < numsolve; ++i)
		  printf("%d %d\n",ss[i].lp,ss[i].rp);
	}
	return 0;
}