NKRACING - Vòng đua F1
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 1e4 + 7;
int n, m, r[N], l[N];
vector<vector<pair<int, int> > > g;
bool vst[N];
void initSet(int n) { for(int i = 0; i < n; ++i) r[i] = i; }
int getSet(int u) { return u == r[u] ? u : r[u] = getSet(r[u]); }
void enter() {
scanf("%d%d",&n,&m); g.resize(n);
for(int i = 0; i < m; ++i) {
int u, v, w; scanf("%d%d%d",&u,&v,&w);
g[--u].push_back(make_pair(--v, w));
g[v].push_back(make_pair(u, w));
}
}
int dfs(const int &u, vector<pair<int, pair<int, int> > > &edge, int &sumEdge) {
int res = 1; vst[u] = true;
TR(g[u], it) {
int v = it->first, w = it->second;
if(!vst[v]) {
edge.push_back(make_pair(w, make_pair(u, v)));
sumEdge += w; l[v] = l[u] + 1;
res += dfs(v, edge, sumEdge);
} else if(l[v] < l[u] - 1) {
edge.push_back(make_pair(w, make_pair(u, v)));
sumEdge += w;
}
}
return res;
}
void solve() {
int res = 0; initSet(n);
for(int u = 0; u < n; ++u) if(!vst[u]) {
vector<pair<int, pair<int, int> > > edge; l[u] = 0;
int n = dfs(u, edge, res), cnt = 1;
sort(edge.begin(), edge.end(), greater<pair<int, pair<int, int> > >());
TR(edge, it) {
int u = it->second.first, v = it->second.second, w = it->first;
if(getSet(u) != getSet(v)) {
res -= w;
r[r[u]] = r[v];
if(++cnt == n) break;
}
}
}
printf("%d\n", res);
}
int main() {
enter();
solve();
return 0;
}