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

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:

  1. O grafo deve ser conexo.
  2. Deve-se minimizar o número de rodovias escolhidas.
  3. 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