Moo Network

Nótese que $0 \le y_i \le 10$. Debe haber una forma de explotar esta restricción.

Intentemos hallar un atajo que nos permita establecer menos aristas al principio asegurando que no se filtren las aristas que deberían pertenecer al MST.

¿Podríamos usar de alguna forma la desigualdad triangular ?

Solución

La subtarea de este problema se puede resolver con fuerza bruta: insertar todas las aristas de los $N$ puntos en una lista de aristas y resolver usando el algoritmo de Kruskal para MST . Mirando más de cerca nuestra solución de fuerza bruta, el verdadero cuello de botella es el tiempo de insertar todas las aristas. Así que nuestro foco debe estar en hallar una forma de explotar la restricción $0 \le y_i \le 10$, de modo que se reduzcan las aristas que hay que insertar.

Dados tres puntos $p_1$, $p_2$ y $p_3$, con coordenadas $(x_1, y_1)$, $(x_2, y_2)$ y $(x_3, y_3)$ respectivamente, donde $x_1 < x_2 < x_3$. Observamos que si $y_1 = y_2$, la longitud de $p_1 p_3$ siempre será mayor que $p_1 p_2$ y $p_2 p_3$ por separado. Si seguimos el algoritmo de Kruskal, consideramos las aristas empezando por la más corta, y solo agregamos una arista al árbol si conecta dos componentes distintas. La arista $p_1 p_3$, al ser la más larga, siempre estará detrás de $p_1 p_2$ y $p_2 p_3$, y cuando le toque, $p_1$ y $p_3$ ya estarán conectados. Así que vemos que $p_1 p_3$ es una arista extraña que podemos quitar con seguridad.

Podemos ignorar sistemáticamente las aristas $p_1 p_3$ barriendo los puntos de izquierda a derecha mientras mantenemos un arreglo de puntos con el mayor valor de $x$ en su carril de $y$. Con cada punto más nuevo, solo insertaremos aristas con puntos de este arreglo. Este enfoque nos permite reducir la complejidad temporal de insertar aristas de $\mathcal{O}(N^2)$ a $\mathcal{O}(N\text{max}(y_i))$.

Implementación

Complejidad temporal: $\mathcal{O}((N\text{max}(y_i))(\text{log}(\text{max}(y_i))+\text{log}(N)))$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAX_Y = 10;
 
// BeginCodeSnip{DSU}
 
ll parent(vector<int> &top, int a) {
	if (top[a] == a) { return a; }
	return top[a] = parent(top, top[a]);
}
 
bool merge(vector<int> &top, vector<int> &sizes, int a, int b) {
	a = parent(top, a);
	b = parent(top, b);
	if (a == b) { return false; }
	if (sizes[b] > sizes[a]) { swap(a, b); }
	top[b] = a;
	sizes[a] += sizes[b];
	return true;
}
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
	// Cada arreglo guarda los valores {x, y, índice} del punto
	vector<array<ll, 3>> points(n);
	for (int i = 0; i < n; i++) {
		cin >> points[i][0] >> points[i][1];
		points[i][2] = i;
	}
	sort(points.begin(), points.end());
 
	// Buffer retiene el punto de mayor x para un valor de y dado
	vector<array<ll, 3>> buffer(11, {-1, -1, -1});
	// Edges guarda una lista de aristas ponderadas
	vector<array<ll, 3>> edges;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= MAX_Y; j++) {
			if (buffer[j][2] != -1) {
				ll dist = pow(points[i][0] - buffer[j][0], 2) +
				          pow(points[i][1] - buffer[j][1], 2);
				edges.push_back({dist, points[i][2], buffer[j][2]});
			}
		}
		buffer[points[i][1]] = points[i];
	}
	sort(edges.begin(), edges.end());
 
	// Lo siguiente es un algoritmo de Kruskal estándar para MST
	ll ans = 0;
	vector<int> top(n);
	vector<int> sizes(n, 1);
	for (int i = 0; i < n; i++) { top[i] = i; }
	for (int i = 0; i < edges.size(); i++) {
		if (merge(top, sizes, edges[i][1], edges[i][2])) { ans += edges[i][0]; }
	}
 
	cout << ans << endl;
}