Segundo mejor árbol de expansión mínima

Un árbol de expansión mínima $T$ es un árbol del grafo dado $G$ que cubre todos los vértices del grafo dado y tiene la suma mínima de pesos de todas las aristas, entre todos los árboles de expansión posibles. Un segundo mejor MST $T’$ es un árbol de expansión que tiene la segunda suma mínima de pesos de todas las aristas, entre todos los árboles de expansión posibles del grafo $G$ .

Observación

Sea $T$ el árbol de expansión mínima de un grafo $G$ . Se puede observar que el segundo mejor árbol de expansión mínima difiere de $T$ en el reemplazo de una sola arista. (Para una demostración de esta afirmación, consultar el problema 23-1 aquí ).

Así que necesitamos encontrar una arista $e_{new}$ que no está en $T$ , y reemplazarla por una arista de $T$ (llámesela $e_{old}$ ) de modo que el grafo nuevo $T’ = (T \cup {e_{new}}) \setminus {e_{old}}$ sea un árbol de expansión y la diferencia de pesos ( $e_{new} - e_{old}$ ) sea mínima.

Usando el algoritmo de Kruskal

Podemos usar el algoritmo de Kruskal para encontrar primero el MST, y luego simplemente intentar quitar una sola arista de él y reemplazarla por otra.

Ordenar las aristas en $O(E \log E)$ , y luego encontrar un MST usando Kruskal en $O(E)$ .
Para cada arista del MST (tendremos $V-1$ aristas en él) excluirla temporalmente de la lista de aristas para que no se pueda elegir.
Luego, intentar de nuevo encontrar un MST en $O(E)$ usando las aristas restantes.
Hacer esto para todas las aristas del MST, y tomar el mejor de todos.

Nota: no hace falta volver a ordenar las aristas en el paso 3.

Así, la complejidad temporal total será $O(E \log V + E + V E)$ = $O(V E)$ .

Modelado como un problema de ancestro común más bajo (LCA)

En el enfoque anterior intentamos todas las posibilidades de quitar una arista del MST. Aquí haremos exactamente lo contrario. Intentamos agregar cada arista que aún no está en el MST.

Ordenar las aristas en $O(E \log E)$ , y luego encontrar un MST usando Kruskal en $O(E)$ .
Para cada arista $e$ que aún no está en el MST, agregarla temporalmente al MST, creando un ciclo. El ciclo pasará por el LCA.
Encontrar la arista $k$ de peso máximo en el ciclo que no es igual a $e$ , siguiendo los padres de los nodos de la arista $e$ , hasta el LCA.
Quitar $k$ temporalmente, creando un nuevo árbol de expansión.
Calcular la diferencia de pesos $\delta = weight(e) - weight(k)$ , y recordarla junto con la arista cambiada.
Repetir el paso 2 para todas las demás aristas, y devolver el árbol de expansión con la menor diferencia de peso respecto del MST.

La complejidad temporal del algoritmo depende de cómo calculemos las $k$ , que son las aristas de peso máximo en el paso 2 de este algoritmo. Una forma de calcularlas de manera eficiente en $O(E \log V)$ es transformar el problema en un problema de ancestro común más bajo (LCA).

Preprocesaremos el LCA enraizando el MST y también calcularemos los pesos máximos de arista para cada nodo en los caminos hacia sus ancestros. Esto se puede hacer usando binary lifting (elevación binaria) para LCA.

La complejidad temporal final de este enfoque es $O(E \log V)$ .

Por ejemplo:

En la imagen, a la izquierda está el MST y a la derecha el segundo mejor MST.

En el grafo dado, supongamos que enraizamos el MST en el vértice azul de arriba, y luego ejecutamos nuestro algoritmo empezando a tomar las aristas que no están en el MST. Sea la primera arista tomada la arista $(u, v)$ de peso 36. Agregar esta arista al árbol forma un ciclo 36 - 7 - 2 - 34.

Ahora encontraremos la arista de peso máximo en este ciclo hallando el $\text{LCA}(u, v) = p$ . Calculamos la arista de peso máximo en los caminos de $u$ a $p$ y de $v$ a $p$ . Nota: el $\text{LCA}(u, v)$ también puede ser igual a $u$ o a $v$ en algún caso. En este ejemplo obtendremos la arista de peso 34 como arista de peso máximo en el ciclo. Al quitar la arista obtenemos un nuevo árbol de expansión, que tiene una diferencia de peso de solo 2.

Después de hacer esto también con todas las demás aristas que no forman parte del MST inicial, podemos ver que este árbol de expansión también era el segundo mejor árbol de expansión en general. Elegir la arista de peso 14 aumentará el peso del árbol en 7, elegir la arista de peso 27 lo aumenta en 14, elegir la arista de peso 28 lo aumenta en 21, y elegir la arista de peso 39 aumentará el árbol en 5.

Implementación


struct edge {
    int s, e, w, id;
    bool operator<(const struct edge& other) { return w < other.w; }
};
typedef struct edge Edge;
 
const int N = 2e5 + 5;
long long res = 0, ans = 1e18;
int n, m, a, b, w, id, l = 21;
vector<Edge> edges;
vector<int> h(N, 0), parent(N, -1), size(N, 0), present(N, 0);
vector<vector<pair<int, int>>> adj(N), dp(N, vector<pair<int, int>>(l));
vector<vector<int>> up(N, vector<int>(l, -1));
 
pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
    vector<int> v = {a.first, a.second, b.first, b.second};
    int topTwo = -3, topOne = -2;
    for (int c : v) {
        if (c > topOne) {
            topTwo = topOne;
            topOne = c;
        } else if (c > topTwo && c < topOne) {
            topTwo = c;
        }
    }
    return {topOne, topTwo};
}
 
void dfs(int u, int par, int d) {
    h[u] = 1 + h[par];
    up[u][0] = par;
    dp[u][0] = {d, -1};
    for (auto v : adj[u]) {
        if (v.first != par) {
            dfs(v.first, u, v.second);
        }
    }
}
 
pair<int, int> lca(int u, int v) {
    pair<int, int> ans = {-2, -3};
    if (h[u] < h[v]) {
        swap(u, v);
    }
    for (int i = l - 1; i >= 0; i--) {
        if (h[u] - h[v] >= (1 << i)) {
            ans = combine(ans, dp[u][i]);
            u = up[u][i];
        }
    }
    if (u == v) {
        return ans;
    }
    for (int i = l - 1; i >= 0; i--) {
        if (up[u][i] != -1 && up[v][i] != -1 && up[u][i] != up[v][i]) {
            ans = combine(ans, combine(dp[u][i], dp[v][i]));
            u = up[u][i];
            v = up[v][i];
        }
    }
    ans = combine(ans, combine(dp[u][0], dp[v][0]));
    return ans;
}
 
int main(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> w; // indexación desde uno
        edges.push_back({a, b, w, i - 1});
    }
    sort(edges.begin(), edges.end());
    for (int i = 0; i <= m - 1; i++) {
        a = edges[i].s;
        b = edges[i].e;
        w = edges[i].w;
        id = edges[i].id;
        if (unite_set(a, b)) { 
            adj[a].emplace_back(b, w);
            adj[b].emplace_back(a, w);
            present[id] = 1;
            res += w;
        }
    }
    dfs(1, 0, 0);
    for (int i = 1; i <= l - 1; i++) {
        for (int j = 1; j <= n; ++j) {
            if (up[j][i - 1] != -1) {
                int v = up[j][i - 1];
                up[j][i] = up[v][i - 1];
                dp[j][i] = combine(dp[j][i - 1], dp[v][i - 1]);
            }
        }
    }
    for (int i = 0; i <= m - 1; i++) {
        id = edges[i].id;
        w = edges[i].w;
        if (!present[id]) {
            auto rem = lca(edges[i].s, edges[i].e);
            if (rem.first != w) {
                if (ans > res + w - rem.first) {
                    ans = res + w - rem.first;
                }
            } else if (rem.second != -1) {
                if (ans > res + w - rem.second) {
                    ans = res + w - rem.second;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Referencias

Competitive Programming-3, by Steven Halim
web.mit.edu

Problemas

Codeforces - Minimum spanning tree for each edge