题目链接:
http://www.lydsy.com/JudgeOnline/problem.php?id=1083
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn = ;
const int maxm = maxn*maxn; struct Edge {
int u, v, w;
bool operator < (const Edge& tmp) const {
return w < tmp.w;
}
}egs[maxm]; int n, m; int fat[maxn];
int Find(int x) {
return fat[x] = fat[x] == x ? x : Find(fat[x]);
} int main() {
while (scanf("%d%d", &n, &m) == ) {
for (int i = ; i <= n; i++) fat[i] = i;
for (int i = ; i < m; i++) {
scanf("%d%d%d", &egs[i].u, &egs[i].v,&egs[i].w);
}
sort(egs, egs + m);
int ma = -;
for (int i = ; i < m; i++) {
int pu = Find(egs[i].u);
int pv = Find(egs[i].v);
if (pu != pv) {
ma = max(ma, egs[i].w);
fat[pv] = pu;
}
}
printf("%d %d\n", n - , ma);
}
return ;
}