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;
}

Download