NKCITY - Xây dựng thành phố
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
#define fi first
#define se second
int r[1005];
i3 g[10005];
int n, m;
int getRoot( int u ) {
return r[u] == u ? u : r[u] = getRoot(r[u]);
}
int main() {
scanf( "%d%d", &n, &m );
for( int i = 0; i < m; ++i ) {
scanf( "%d%d%d", &g[i].se.fi, &g[i].se.se, &g[i].fi );
--g[i].se.fi; --g[i].se.se;
}
for( int i = 0; i < n; ++i ) r[i] = i;
sort(g, g+m);
int numE = 0, res;
for( int i = 0; i < m && numE < n; ++i ) {
int l = g[i].fi, u = g[i].se.fi, v = g[i].se.se;
if (getRoot(u) != getRoot(v)) {
res = l;
r[r[u]] = r[v];
++numE;
}
}
printf( "%d\n", res );
return 0;
}