Copa do Mundo OBI 2014

copa.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 115;

int n, f, r;
vector<tuple<int, int, int, int>> arestas; // tipo, peso, vertice 1, vertice 2
int pai[MAXN], sze[MAXN]; 		       // vetores do Union-Find

int find(int u)
{
	if(pai[u] == u) return u;
	return pai[u] = find(pai[u]);
}

bool join(int u, int v) // retorna 1 se juntei, 0 caso contrário
{ 
	u = find(u), v = find(v);
	if(u == v) return false; // já estão na mesma componente

	if(sze[u] < sze[v]) swap(u, v);
	pai[v] = u; sze[u] += sze[v];
	return true;
}

int main()
{
 	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> f >> r;

	for(int i = 1; i <= f; i++){ // ferrovias
		int a, b, c; cin >> a >> b >> c;
		arestas.emplace_back(1, c, a, b); 
	}

	for(int i = 1; i <= r; i++){ // rodovias
		int a, b, c; cin >> a >> b >> c;
		arestas.emplace_back(2, c, a, b); 
	}

	// As arestas serão ordenadas primeiro por tipo e depois por peso
	sort(arestas.begin(), arestas.end());

	for(int i = 1; i <= n; i++) // Inicializo a DSU
		sze[i] = 1, pai[i] = i;

	int custoTotal = 0;

	for(auto [tipo, peso, u, v] : arestas) // Computo o custo
		if(join(u, v)) custoTotal += peso;

	cout << custoTotal << '\n';
}