Portals

Solución 1 - Kruskal

Explicación

Primero notamos que el movimiento se define en términos de portales, así que principalmente nos importa cómo están conectados los portales.

Consideremos el multigrafo no dirigido $G$ con $2N$ nodos tal que:

Cada portal del grafo original corresponde a un nodo en $G$
Cada nodo $v$ del grafo original corresponde a las aristas $p_{v,0} \leftrightarrow p_{v,1}$ y $p_{v,2} \leftrightarrow p_{v,3}$ en $G$

Observamos que cada nodo en $G$ tiene grado exactamente dos, así que $G$ es una unión de ciclos disjuntos. Así, nuestro objetivo es unir todos los nodos de $G$ en un solo ciclo.

Supongamos que los portales $p_{v,0}$ y $p_{v,1}$ no están contenidos en el mismo ciclo que $p_{v,2}$ y $p_{v,3}$ en $G$ .

Entonces, permutando los portales adyacentes al nodo $v$ de modo que la lista de adyacencia quede $p_{v,0}, p_{v,2}, p_{v,1}, p_{v,3}$ , podemos combinar todos $p_{v,0}, p_{v,1}, p_{v,2}, p_{v,3}$ en un solo ciclo. En esencia, cada nodo puede unir dos ciclos.

Nótese que al reemplazar “ciclos” por “componentes conexas” arriba, se nos invita a hallar un árbol de expansión mínima (MST). En otras palabras, queremos unir todas las componentes conexas disjuntas de modo que $G$ quede conexo.

Ahora, consideremos el grafo $G'$ con los mismos nodos que $G$ y los siguientes costos:

Para cada nodo $v$ , las aristas $p_{v,0} \leftrightarrow p_{v,1}$ y $p_{v,2} \leftrightarrow p_{v,3}$ tienen costo $0$
Para cada nodo $v$ , la arista $p_{v,0} \leftrightarrow p_{v,2}$ tiene costo $c_v$ moonies

En concreto, la respuesta es el costo del MST de $G'$ , que se puede hallar usando el algoritmo de Kruskal o el algoritmo de Prim.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
struct Edge {
	int from, to, cost;
};
const int MAX_N = 100000;
int parent[MAX_N * 2];
int comp_size[MAX_N * 2];
 
// BeginCodeSnip{Standard DSU operations}
void init(int n) {
	for (int i = 0; i < n; i++) {
		parent[i] = i;
		comp_size[i] = 1;
	}
}
 
int find(int a) {
	if (a == parent[a]) { return a; }
	return parent[a] = find(parent[a]);
}
 
bool unite(int a, int b) {
	int root_a = find(a), root_b = find(b);
	if (root_a == root_b) { return false; }
	if (comp_size[root_a] > comp_size[root_b]) { swap(root_a, root_b); }
	parent[root_a] = root_b;
	comp_size[root_b] += comp_size[root_a];
	return true;
}
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
	init(n * 2);
	int cost, p1, p2, p3, p4;
	vector<Edge> edges;
	for (int i = 0; i < n; i++) {
		cin >> cost >> p1 >> p2 >> p3 >> p4;
		// una arista de p1 a p2 o de p3 a p4 tiene costo 0
		edges.push_back({p1 - 1, p2 - 1, 0});
		edges.push_back({p3 - 1, p4 - 1, 0});
		// para obtener una arista de p1 a p3, hay que pagar para permutar los portales
		edges.push_back({p1 - 1, p3 - 1, cost});
	}
 
	// ordenamos las aristas en orden creciente de costo
	sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.cost < b.cost; });
 
	int min_cost = 0;
	for (Edge edge : edges) {
		if (unite(edge.from, edge.to)) { min_cost += edge.cost; }
	}
	cout << min_cost << endl;
}

Solución 2 - Prim

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
const int MAX_N = 100000;
struct Node {
	int vertex, cost;
	bool operator>(Node other) const { return cost > other.cost; }
};
int main() {
	int n;
	cin >> n;
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	vector<Node> adj[2 * MAX_N];
	for (int i = 0; i < n; i++) {
		int cost, p1, p2, p3, p4;
		cin >> cost >> p1 >> p2 >> p3 >> p4;
		p1--;
		p2--;
		p3--;
		p4--;
		// una arista que conecta p1 y p2 o que conecta p3 y p4 tiene costo 0
		adj[p1].push_back({p2, 0});
		adj[p2].push_back({p1, 0});
		adj[p3].push_back({p4, 0});
		adj[p4].push_back({p3, 0});
		// para obtener una arista de p1 a p3, hay que pagar para permutar los portales
		adj[p1].push_back({p3, cost});
		adj[p3].push_back({p1, cost});
	}
	pq.push({0, 0});
	bool visited[2 * MAX_N]{};
	int min_cost = 0;
	// usamos Prim para hallar el MST
	while (!pq.empty()) {
		int curr = pq.top().vertex, cost = pq.top().cost;
		pq.pop();
		if (visited[curr]) { continue; }
		visited[curr] = true;
		min_cost += cost;
		// agregamos aristas desde el vértice actual visitado hacia vértices no visitados
		for (Node next : adj[curr]) {
			if (!visited[next.vertex]) { pq.push(next); }
		}
	}
	cout << min_cost << endl;
}