Fluxo máximo - algoritmo de Dinic

O algoritmo de Dinic resolve o problema do fluxo máximo em $O(V^2E)$. O problema do fluxo máximo é definido neste artigo: Fluxo máximo - Ford-Fulkerson e Edmonds-Karp. Este algoritmo foi descoberto por Yefim Dinitz em 1970.

Definições

Uma rede residual $G^R$ de uma rede $G$ é uma rede que contém duas arestas para cada aresta $(v, u)\in G$:

Um fluxo de bloqueio de alguma rede é um fluxo em que todos os caminhos de $s$ a $t$ contêm pelo menos uma aresta saturada por esse fluxo. Observe que um fluxo de bloqueio não é necessariamente máximo.

Uma rede em camadas de uma rede $G$ é uma rede construída da seguinte maneira. Primeiramente, para cada vértice $v$ calculamos o $level[v]$ - o caminho mais curto (sem pesos) de $s$ para esse vértice usando apenas arestas com capacidade positiva. Então, mantemos apenas as arestas $(v, u)$ para as quais $level[v] + 1 = level[u]$. Essa rede é acíclica.

Algoritmo

O algoritmo consiste em várias fases. Em cada fase, construímos a rede em camadas da rede residual de $G$. Em seguida, encontramos um fluxo de bloqueio arbitrário na rede em camadas e o adicionamos ao fluxo atual.

Prova

Vamos mostrar que, se o algoritmo terminar, ele encontrará o fluxo máximo.

Se o algoritmo terminasse, não seria possível encontrar um fluxo de bloqueio na rede em camadas. Isso significa que a rede em camadas não possui nenhum caminho de $s$ a $t$. Consequentemente, isso significa que a rede residual não possui um caminho de $s$ a $t$. Finalmente, isso irá significar que o fluxo é máximo.

Número de fases

O algoritmo termina em menos de $V$ fases. Para provar isso, precisamos primeiro provar dois lemas.

Lema 1. As distâncias a partir de $s$ a cada vértice não diminuem após cada iteração, ou seja $level_{i+1}[v] \ge level_i[v]$.

Prova. Fixe uma fase $i$ e um vértice $v$. Considere qualquer caminho mais curto $P$ de $s$ a $v$ em $G_{i+1}^R$. O comprimento de $P$ é igual a $level_{i+1}[v]$. Note que $G_{i+1}^R$ só pode conter arestas de $G_i^R$ e back edges(arestas de retorno) para arestas de $G_i^R$. Se $P$ não tiver arestas de retorno para $G_i^R$, então $level_{i+1}[v] \ge level_i[v]$ porque $P$ também é um caminho em $G_i^R$. Agora, suponha que $P$ tenha pelo menos uma aresta de retorno. Seja a primeira dessas arestas: $(u, w)$. Assim, $level_{i+1}[u] \ge level_i[u]$ (por causa do primeiro caso). A aresta $(u, w)$ não pertence a $G_i^R$, então a aresta $(w, u)$ foi afetada pelo fluxo de bloqueio na iteração anterior. Isso significa que $level_i[u] = level_i[w] + 1$. Também: $level_{i+1}[w] = level_{i+1}[u] + 1$. A partir dessas duas equações e $level_{i+1}[u] \ge level_i[u]$ obtemos $level_{i+1}[w] \ge level_i[w] + 2$. Agora podemos usar a mesma idéia para o resto do caminho.

Lema 2. $level_{i+1}[t] > level_i[t]$

Prova. Do lema anterior, $level_{i+1}[t] \ge level_i[t]$. Suponha que $level_{i+1}[t] = level_i[t]$. Note que $G_{i+1}^R$ só pode conter arestas de $G_i^R$ e arestas de retorno para arestas de $G_i^R$. Isso significa que existe um caminho mais curto em $G_i^R$ que não foi bloqueado pelo fluxo de bloqueio, isso é uma contradição.

Desses dois lemas, concluímos que há menos de $V$ fases porque $level[t]$ aumenta, mas não pode ser maior que $V - 1$.

Localizando fluxo de bloqueio

Para encontrar o fluxo de bloqueio em cada iteração, podemos simplesmente tentar empurrar o fluxo com a DFS a partir de $s$ a $t$ na rede em camadas enquanto ele pode ser empurrado. Para fazer isso mais rapidamente, precisamos remover as arestas que não podem mais ser usadas para empurrar. Para fazer isso, podemos manter um ponteiro em cada vértice que aponta para a próxima aresta que pode ser usada. Cada ponteiro pode ser movido no máximo $E$ vezes, assim, cada fase funciona em $O(VE)$.

Complexidade

Como há menos de $V$ fases, a complexidade total é de $O(V^2E)$.

Redes de unidades

Uma rede de unidade é uma rede na qual todas as arestas têm capacidade unitária e, para qualquer vértice, exceto $s$ e $t$ a aresta de entrada ou de saída é única. Esse é exatamente o caso da rede que construímos para resolver o problema máximo de correspondência com os fluxos.

Nas redes de unidades, o algoritmo do Dinic funciona em $O(E\sqrt{V})$. Vamos provar isso.

Primeiro, cada fase agora funciona em $O(E)$ porque cada aresta será considerada no máximo uma vez.

Segundo, suponha que já existam $\sqrt{V}$ fases. Então, todos os augmenting paths de tamanho $\le\sqrt{V}$ foram encontrados. Seja $f$ o fluxo atual, $f'$ seja o fluxo máximo. Considere a diferença entre eles $f' - f$. É um fluxo em $G^R$ de valor $|f'| - |f|$ e em cada aresta será $0$ ou $1$. Pode ser decomposto em $|f'| - |f|$ caminhos de $s$ a $t$ e possivelmente ciclos. Como a rede é unitária, eles não podem ter vértices comuns; portanto, o número total de vértices é $\ge (|f'| - |f|)\sqrt{V}$, mas também é $\le V$, assim, nas outras $\sqrt{V}$ iterações definitivamente encontraremos o fluxo máximo.

Implementação

struct FlowEdge {
    int v, u;
    long long cap, flow = 0;
    FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
    const long long flow_inf = 1e18;
    vector<FlowEdge> edges;
    vector<vector<int>> adj;
    int n, m = 0;
    int s, t;
    vector<int> level, ptr;
    queue<int> q;

    Dinic(int n, int s, int t) : n(n), s(s), t(t) {
        adj.resize(n);
        level.resize(n);
        ptr.resize(n);
    }

    void add_edge(int v, int u, long long cap) {
        edges.emplace_back(v, u, cap);
        edges.emplace_back(u, v, 0);
        adj[v].push_back(m);
        adj[u].push_back(m + 1);
        m += 2;
    }

    bool bfs() {
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int id : adj[v]) {
                if (edges[id].cap - edges[id].flow < 1)
                    continue;
                if (level[edges[id].u] != -1)
                    continue;
                level[edges[id].u] = level[v] + 1;
                q.push(edges[id].u);
            }
        }
        return level[t] != -1;
    }

    long long dfs(int v, long long pushed) {
        if (pushed == 0)
            return 0;
        if (v == t)
            return pushed;
        for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
            int id = adj[v][cid];
            int u = edges[id].u;
            if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
                continue;
            long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
            if (tr == 0)
                continue;
            edges[id].flow += tr;
            edges[id ^ 1].flow -= tr;
            return tr;
        }
        return 0;
    }

    long long flow() {
        long long f = 0;
        while (true) {
            fill(level.begin(), level.end(), -1);
            level[s] = 0;
            q.push(s);
            if (!bfs())
                break;
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, flow_inf)) {
                f += pushed;
            }
        }
        return f;
    }
};