Skip to Content
CTRL K

Design Tutorial Inverse the Problem

Análisis oficial 

Explicación

Esto puede parecer un poco deus ex machina, pero podemos afirmar lo siguiente:

La arista de longitud mínima debe pertenecer al árbol ponderado y, en general, la kk-ésima arista de longitud mínima que conecta los nodos AA y BB pertenece al árbol si y solo si aún no hay un camino entre ellos.

¿Por qué? Bueno, como consideramos las aristas en orden no decreciente de peso, que AA y BB ya compartan un camino implicaría que se pueden conectar por aristas de longitud menor que la kk-ésima arista de longitud mínima.

Nótese cuán similar es esta idea de considerar aristas en orden de peso no decreciente y agregar aristas entre nodos desconectados al algoritmo de Kruskal. Esto nos da la idea de que si la matriz de distancias dada es de un árbol ponderado, ¡entonces ese árbol ponderado debe ser el árbol de expansión mínima (MST) del grafo original, dado por la matriz de distancias!

Por lo tanto, primero debemos hallar el MST y luego comprobar si las distancias entre los nodos de este árbol coinciden con la matriz de distancias dada. Para comprobar distancias entre nodos, usamos DFS; sin embargo, BFS y otros métodos también sirven.

Implementación

Complejidad temporal: O(N2log⁡N)\mathcal{O}(N^2\log N) con el MST de Kruskal o O(N2)\mathcal{O}(N^2) con Prim N2N^2.

#include <bits/stdc++.h>
using namespace std;
 
 
using ll = long long;
 
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
 
using pii = pair<int, int>;  // note pii, not pi
#define f first
#define s second
#define mp make_pair
 
const int MX = 2e3 + 10;
 
int dist[MX][MX], n, par[MX], sz[MX];
vector<pii> adj[MX];
vector<pair<int, pii>> edges;
 
int find(int x) {
	if (x != par[x]) par[x] = find(par[x]);
	return par[x];
}
 
void Union(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
}
 
void mkdsu() {
	for (int i = 0; i <= n; i++) { par[i] = i, sz[i] = 1; }
}
 
bool cmp(const pair<int, pii> &a, const pair<int, pii> &b) { return a.f < b.f; }
 
void kruskals() {
	int tot = 0;
	mkdsu();
	sort(all(edges), cmp);
	for (const auto &e : edges) {
		if (tot == n) break;
		int u = e.s.f, v = e.s.s, w = e.f;
		if (find(u) != find(v)) {
			Union(u, v);
			tot = max(tot, sz[find(u)]);
			adj[u].pb(mp(v, w));
			adj[v].pb(mp(u, w));
		}
	}
}
 
bool dfs(int u, int p, int src, int d) {
	if (dist[src][u] != d || (src != u && dist[src][u] == 0)) return false;
	bool ans = 1;
	for (const auto &e : adj[u]) {
		if (e.f == p) continue;
		ans &= dfs(e.f, u, src, d + e.s);
	}
	return ans;
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	bool ans = 1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> dist[i][j];
			if (i != j) {
				if (j < i && dist[i][j] != dist[j][i]) ans = 0;
				if (i < j) edges.pb(mp(dist[i][j], mp(i, j)));
			} else {
				if (dist[i][j] != 0) ans = 0;
			}
		}
	}
 
	kruskals();
 
	for (int i = 1; i <= n; i++) { ans &= dfs(i, 0, i, 0); }
 
	if (ans) cout << "YES\n";
	else cout << "NO\n";
 
	return 0;
}
Fundamentos