Segunda melhor Árvore Geradora Mínima

A Árvore Geradora Mínima $T$ é uma árvore para o grafo $G$ que se estende por todos os vértices do grafo fornecido e possui a soma mínima de peso de todas as arestas, de todas as árvores geradoras possíveis. Uma segunda melhor MST $T'$ é uma árvore geradora, que possui a segunda soma mínima de peso de todas as arestas, de todas as árvore geradoras do grafo $G$.

Observação

Seja $T$ a Árvore Geradora Mínima(MST) de um grafo $G$. Pode ser observado que a segunda melhor Árvore Geradora Mínima difere de $T$ por apenas uma substituição de aresta. (Para uma prova desta declaração, consulte o problema 23-1 aqui).

Portanto, precisamos encontrar uma aresta $e_{new}$ que não esteja em $T$, e substituí-la por uma aresta em $T$ (seja $e_{old}$) de modo que o novo grafo $T' = (T \cup \{e_{new}\}) \setminus \{e_{old}\}$ é uma árvore geradora e a diferença dos pesos ($e_{new} - e_{old}$) seja mínima.

Usando o algoritmo de Kruskal

Podemos usar o algoritmo de Kruskal para encontrar a MST primeiro e, em seguida, apenas tentar remover uma única aresta dela e substituí-lo por outro.

  1. Ordenar as arestas em $O(E \log E)$, então encontrar a MST usando Kruskal em $O(E)$.
  2. Para cada aresta na MST (teremos $V-1$ arestas nela) exclua-a temporariamente da lista de arestas para que não possa ser escolhida.
  3. Em seguida, tente novamente encontrar uma MST em $O(E)$ usando as arestas restantes.
  4. Faça isso para todas as arestas da MST e tire a melhor de todas.

Nota: não precisamos ordenar as arestas novamente na etapa 3.

Portanto, a complexidade geral do tempo será $O(E \log V + E + V E)$ = $O(V E)$.

Modelando em um problema de menor ancestral comum (LCA)

Na abordagem anterior, tentamos todas as possibilidades de remover uma aresta do MST. Aqui vamos fazer exatamente o oposto. Tentamos adicionar todas as arestas que ainda não estão no MST.

  1. Ordene as arestas em $O(E \log E)$, e então encontre a MST usando Kruskal em $O(E)$.
  2. Para cada aresta $e$ que ainda não está na MST, temporariamente adicione na MST, criando um ciclo.
  3. Encontre a aresta $k$ com peso máximo no ciclo que não seja igual a $e$.
  4. Remova $k$ temporariamente, criando uma nova árvore geradora.
  5. Calcule a diferença de peso $\delta = peso(e) - peso(k)$, e lembre-se dele juntamente com a aresta alterada.
  6. Repita a etapa 2 para todas as outras arestas e retorne a árvore geradora com a menor diferença de peso ao MST.

A complexidade do tempo do algoritmo depende de como calculamos os $k$'s, que são as arestas de peso máximo na etapa 2 deste algoritmo. Uma maneira de computá-los eficientemente em $O(E \log V)$ é transformar o problema em um problema de menor ancestral comum (LCA).

Nós pré-processaremos o LCA fazendo o enraizamento na MST e também calcularemos os pesos máximos das arestas de cada nó nos caminhos para seus ancestrais. Isso pode ser feito usando "Binary Lifting" para o LCA.

A complexidade de tempo final dessa abordagem é $O(E \log V)$.

Por exemplo:

MST Second best MST

Na imagem à esquerda está a MST e à direita a segundo melhor MST.

No dado grafo suponha que enraizamos a MST no vértice azul do topo, e em seguida, executamos o algoritmo começando a escolher as arestas que não estão no MST. Deixe a aresta escolhida primeiro ser a aresta $(u, v)$ com peso 36. A adição dessa aresta à árvore forma um ciclo 36 - 7 - 2 - 34.

Agora, encontraremos a aresta de peso máximo no ciclo encontrando o $\text{LCA}(u, v) = p$. Calculamos a aresta de peso máximo nos caminhos de $u$ para $p$ e de $v$ para $p$. Nota: o $\text{LCA}(u, v)$ pode também ser igual a $u$ ou $v$ em algum caso. Neste exemplo, obteremos a aresta com peso 34 como a aresta de peso máximo no ciclo. Ao remover a aresta, obtemos uma nova árvore geradora, que tem uma diferença de peso de apenas 2.

Depois de fazer isso também com todas as outras arestas que não fazem parte da MST inicial, podemos ver que essa árvore geradora também é a segunda melhor árvore geradora no geral. Escolher a aresta com peso 14 aumentará o peso da árvore em 7, escolher a aresta com peso 27 aumenta em 14, escolher a aresta com peso 28 aumenta em 21 e escolher a aresta com peso 39 aumentará a árvore em 5.

Implementação

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; 
        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;
}

Referências

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

Problemas