Solução: Shichikuji and Power Grid

São dadas $N$ cidades, cada uma representada por um ponto no plano cartesiano (vale notar que um único ponto pode conter mais de uma cidade). Deve-se fornecer eletricidade a cada cidade construindo uma usina na cidade ou fazendo uma conexão entre ela e outra que já tenha eletricidade. Em outras palavras, uma dada cidade tem eletricidade se nela existir uma usina ou se estiver conectada a uma outra cidade que tenha eletricidade por uma conexão (direta ou indireta). Queremos computar o mínimo custo para fazer isso, dado que:

A construção de uma usina de energia na cidade $i$ custa $c_i$ reais.
Uma conexão entre a cidade $i$ e a cidade $j$ é feita por fios. Os fios só podem seguir as direções cardeais (norte, sul, leste, oeste), mas podem se cruzar. O custo para conectar as cidades i e j é igual a $(k_i + k_j)$ * $(|x_i - x_j| + |y_i - y_j|)$ .

Uma ideia é que podemos montar um grafo a partir das informações fornecidas. Cada vértice representa uma cidade, e cada aresta entre $(i, j)$ representa o custo de ligar as cidades $i$ e $j$ , ou seja, tem peso $(k_i + k_j) * (|x_i - x_j| + |y_i - y_j|)$ . Montaremos uma aresta desse tipo para todo par de cidades. Porém, ainda estamos desconsiderando as cidades que de fato terão uma usina. Para consertar isso, podemos criar um vértice fictício. Assim, além das arestas já mencionadas, ligamos todas as cidades ao vértice fictício com uma aresta de peso $c_i$ . Basta agora computar a MST do grafo montado.

Para melhor entendimento, veja o grafo considerando o primeiro caso de teste, assim como o código dessa solução. O vértice fictício é representado pelo $0$ :

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

	typedef long long ll;
	const int MAXN = 2e3 + 10;

	ll n, x[MAXN], y[MAXN], c[MAXN], k[MAXN];
	int pai[MAXN], sze[MAXN];

	vector<tuple<ll, int, int>> arestas; // peso, vertice 1, vertice 2

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

	bool join(int u, int v) // retorna true se juntei, false caso contrario
	{
	u = find(u), v = find(v);
	if(u == v) return false; // ja estao na mesma componente

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

	ll calcCusto(int i, int j)
	{
	ll dist = abs(x[i] - x[j]) + abs(y[i] - y[j]);
	return (k[i] + k[j]) * dist;
	}

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

	cin >> n;

	for(int i = 1; i <= n; i++)
	cin >> x[i] >> y[i];

	for(int i = 1; i <= n; i++) cin >> c[i];
	for(int i = 1; i <= n; i++) cin >> k[i];

	//Arestas entre cidades
	for(int i = 1; i <= n; i++)
	for(int j = i + 1; j <= n; j++)
	arestas.emplace_back(calcCusto(i, j), i, j);

	//Aresta com vertice ficticio
	for(int i = 1; i <= n; i++)
	arestas.emplace_back(c[i], i, 0);

	sort(arestas.begin(), arestas.end());

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

	ll custoTotal = 0;
	vector<int> estacoes;
	vector<pair<int, int>> ligacoes;

	for(auto [w, u, v] : arestas){
	if(!join(u, v)) continue; // Nao esta na MST
	custoTotal += w;

	if(v == 0) estacoes.push_back(u);
	else ligacoes.emplace_back(u, v);
	}

	cout << custoTotal << '\n';
	cout << (int) estacoes.size() << '\n';

	for(auto cidade : estacoes)
	cout << cidade << ' ';

	cout << '\n' << (int) ligacoes.size() << '\n';

	for(auto [u, v] : ligacoes)
	cout << u << ' ' << v << '\n';
	}

view raw

shichikuji.cpp

hosted with ❤ by GitHub