Fenced In

Pista 1

Las representaciones de grilla 2D a menudo son difíciles de manejar. ¿Qué pasa si pensamos el problema en términos de un grafo?

Pista 2

Podemos convertir cada uno de los $(n+1)(m+1)$ espacios de la grilla construidos por las $N$ cercas verticales y $M$ cercas horizontales en nodos, y asignar como pesos de arista la longitud del lado compartido entre cada uno de los vecinos de los nodos.

Pista 3

La cantidad mínima de aristas a quitar asegurando que los nodos queden conectados entre sí es exactamente $(n+1)(m+1) - 1$ . Casi como tallar un árbol a partir del grafo que construimos.

Solución

Explicación

Las $n$ cercas verticales y $m$ cercas horizontales dividen el gran pastizal rectangular en $(n+1)(m+1)$ grillas. Para entender mejor el problema, es más fácil visualizar la entrada en términos de un grafo: las propias grillas son los nodos, y las cercas de cada uno de los 4 lados circundantes son las aristas que se pueden construir. Para que una vaca viaje de cualquier nodo a otro, todo lo que necesitamos es construir un árbol.

Para asegurar que las aristas elegidas sean óptimas, construimos un árbol de expansión mínima (MST), que se puede resolver con el algoritmo de Kruskal.

Implementación

Complejidad temporal: $\mathcal{O}((N \cdot \max \{ y_i = 1 .. n \} )(\text{log}(\max \{ y_i = 1 .. n \})+\text{log}(N)))$

C++


#include <bits/stdc++.h>
using namespace std;
 
struct Edge {
	int cost;
	int i;
	int j;
};
 
// BeginCodeSnip{DSU}
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
 
	// obtener el representante de la componente (usa compresión de caminos)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
	bool same_set(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	bool unite(int x, int y) {  // unión por tamaño
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
// EndCodeSnip
 
int main() {
	freopen("fencedin.in", "r", stdin);
	freopen("fencedin.out", "w", stdout);
 
	int hdist, vdist, n, m;
	cin >> hdist >> vdist >> n >> m;
 
	vector<int> vx(n + 1), vy(m + 1);
 
	for (int i = 1; i <= n; i++) { cin >> vx[i]; }
 
	for (int i = 1; i <= m; i++) { cin >> vy[i]; }
 
	vx.push_back(hdist);
	vy.push_back(vdist);
 
	sort(vx.begin(), vx.end());
	sort(vy.begin(), vy.end());
 
	// agregar cercas en los bordes para calcular aristas al frente/atrás
	n += 2;
	m += 2;
 
	/*
	 * numeraremos las secciones de izquierda
	 * a derecha.
	 * 1 2
	 * 3 4
	 */
	vector<Edge> edges;
 
	// aristas de cercas verticales
	int cur_sect = 0, row = 1;
	while (row < m) {
		// todas las cercas verticales en una fila tienen la misma longitud
		for (int i = 0; i < n - 2; i++) {
			edges.push_back(Edge{vy[row] - vy[row - 1], cur_sect, cur_sect + 1});
			cur_sect++;
		}
 
		cur_sect++;
		row++;
	}
 
	// aristas de cercas horizontales
	cur_sect = n - 1;
	int col = 1;
	while (col < n) {
		int init = cur_sect;
		// todas las cercas horizontales en una columna tienen la misma longitud
		for (int i = 0; i < m - 2; i++) {
			edges.push_back(Edge{vx[col] - vx[col - 1], cur_sect - (n - 1), cur_sect});
 
			// bajar una fila
			cur_sect += (n - 1);
		}
		cur_sect = init + 1;
		col++;
	}
 
	// kruskal
	DSU dsu((n + 2) * (m + 2));
 
	sort(edges.begin(), edges.end(),
	     [](const Edge &t, const Edge &y) { return t.cost < y.cost; });
 
	long long ans = 0;
	for (Edge &i : edges) {
		if (dsu.unite(i.i, i.j)) { ans += i.cost; }
	}
	cout << ans << endl;
}