Skip to Content
CTRL K

Check Sum

Análisis oficial 

Explicación

Como el análisis oficial está bien documentado y cubre el problema en su totalidad, léase primero. Las siguientes notas aclaran algunos detalles de la implementación.

  • Primero, notemos que la cantidad de filas y columnas es equivalente a 2N2N, porque la matriz es cuadrada. Por lo tanto, al construir nuestro grafo, podemos simplemente sumar NN para distinguir la fila ii de la columna jj.

Por supuesto, el problema de hallar un conjunto de aristas de peso mínimo que rompe ciclos es equivalente al conocido problema de hallar un bosque de expansión de peso máximo de GG, excepto que construiríamos el conjunto complemento de aristas a conservar en lugar del conjunto de aristas a eliminar.

  • Notemos que las aristas que deberíamos eliminar —las que están resaltadas en el diagrama en rojo— son equivalentes a cualquier arista que no esté incluida en el árbol de expansión máxima del grafo GG. Por lo tanto, nuestra respuesta es equivalente a la diferencia entre la suma total de todas las aristas y las que están en el árbol de expansión máxima.

Implementación

Complejidad temporal: O(N2log⁡N)\mathcal{O}(N^2\log N)

// CodeSnip{CPP Short Template}
 
struct DSU {
	vi e;
	void init(int N) { e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(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 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return 1;
	}
};
 
template <class T> T kruskal(int N, vector<pair<T, pi>> ed) {
	sort(ed.rbegin(), ed.rend());
	T ans = 0;
	DSU D;
	D.init(N);  // las aristas que unen están en el MST
	for (auto a : ed)
		if (D.unite(a.s.f, a.s.s)) ans += a.f;
	return ans;
}
 
void solve(int tc) {
	int n;
	cin >> n;
	vector<vi> A(n, vi(n)), B(n, vi(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> A[i][j];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> B[i][j];
	vi row(n), col(n);
	for (int i = 0; i < n; i++) cin >> row[i];
	for (int i = 0; i < n; i++) cin >> col[i];
	vector<pair<int, pi>> edges;
	int total = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (A[i][j] == -1) {
				// n + j se usa para distinguir filas de columnas
				edges.pb({B[i][j], {i, n + j}});
				total += B[i][j];
			}
		}
	cout << "Case #" << tc << ": " << total - kruskal(2 * n, edges) << "\n";
}
int main() {
	setIO();
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) solve(i);
}
Fundamentos