NKRACING - Vòng đua F1
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
pair<int, pair<int,int> > a[100010];
int F[10010], result;
int main() {
scanf("%d%d", &n, &m);
for(int i=0;i<m;++i) scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
sort( a, a+m);
memset( F, -1, sizeof(F));
for(int i=m-1;i>=0;--i) {
int c = a[i].first;
int u = a[i].second.first;
int v = a[i].second.second;
result += c;
while(F[u]>=0) u = F[u];
while(F[v]>=0) v = F[v];
//cout << c << endl;
if(u==v) continue;
result -= c;
if(F[u]>=F[v]) swap( u, v);
F[u] += F[v];
F[v] = u;
}
cout << result << endl;
//system("pause");
return 0;
}