Solução: Copa do Mundo (OBI 2014)

Dado um grafo não direcionado com pesos e arestas de dois tipos (rodovias e ferrovias), devemos escolher um subconjunto de arestas de tal forma que, considerando o grafo apenas com as arestas escolhidas, as seguintes condições sejam satisfeitas:

O grafo deve ser conexo.
Deve-se minimizar o número de rodovias escolhidas.
Dentre as escolhas que satisfazem as restrições 1 e 2, deve-se escolher uma que minimize a soma dos pesos.

Se não fosse pelo fato das arestas terem dois tipos, bastaria aplicar algum algoritmo de MST e somar os pesos das arestas escolhidas. Nesse problema, porém, queremos dar prioridade às ferrovias, mesmo que isso não gere o verdadeiro custo mínimo. Entretanto, podemos fazer uma pequena modificação no algoritmo de Kruskal para que ele considere essa maior prioridade: basta processar todas as ferrovias antes de todas as rodovias. Segue o código para melhor entendimento:

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

view raw

copa.cpp

hosted with ❤ by GitHub