题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1083
代码(难得的BZ水题。。。):
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
struct saver {
int s,t,d;
} edge[MAXN];
bool cmp(saver x,saver y) {
return x.d<y.d;
}
int n,m,father[MAXN];
int Find(int x) {
int i,j=x;
for (i=x;father[i];i=father[i]);
while (father[j]) {
int k=father[j];
father[j]=i;
j=k;
}
return i;
}
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++) scanf("%d%d%d",&edge[i].s,&edge[i].t,&edge[i].d);
sort(edge,edge+m,cmp);
memset(father,0,sizeof(father));
printf("%d ",n-1);
for (int i=0;i<m;i++) {
if (Find(edge[i].s)!=Find(edge[i].t)){
father[Find(edge[i].s)]=Find(edge[i].t);
if ((--n)==1) {
printf("%d\n",edge[i].d);
return 0;
}
}
}
return 0;
}