NKCITY - Xây dựng thành phố
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<pair<int, pair<int,int> > > vec;
int n, m;
scanf("%d%d", &n, &m);
for(int i=0;i<m ;++i) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
vec.push_back( make_pair( c, make_pair( u, v)));
}
int f[n+1], res = 0;
memset( f, -1, sizeof(int) * (n+1));
sort( vec.begin(), vec.end());
for(int i=0;i<vec.size();++i) {
int u = vec[i].second.first;
int v = vec[i].second.second;
int c = vec[i].first;
while(f[u]>=0) u = f[u];
while(f[v]>=0) v = f[v];
if(u!=v) {
res = c;
f[u] += f[v];
f[v] = u;
}
}
printf("%d\n", res);
return 0;
}