Introduction aux flux

Un réseau de flot est un graphe orienté G = (V, E) avec une source s et un puits t. Chaque arête (u, v) possède une capacité c(u, v) ≥ 0. Un flot f est une fonction qui associe à chaque arête une valeur f(u, v) vérifiant :

• Contrainte de capacité : 0 ≤ f(u, v) ≤ c(u, v)
• Conservation du flot : pour tout sommet x autre que s et t, la somme des flots entrants est égale à la somme des flots sortents.

La valeur du flot est le flot total sortant de s (ou entrant dans t). Le flot maximum est la valeur maximale possible.

Réseau résiduel

À partir d’un flot f, on construit le réseau résiduel Gf : même ensemble de sommets, et pour chaque arête (u, v) du graphe original :

• On conserve une arête (u, v) de capacité résiduelle c(u, v) - f(u, v) si cette valeur est positive.
• On ajoute une arête inverse (v, u) de capacité f(u, v).

Chemin augmentant

Un chemin de s à t dans le réseau résiduel est apelé chemin augmentant. On peut alors augmenter le flot le long de ce chemin.

Coupe

Une coupe (S, T) partitionne V en deux ensembles avec s ∈ S et t ∈ T. La capacité de la coupe est la somme des capacités des arêtes allant de S vers T. Le théorème flot-max/coupe-min énonce que la valeur du flot maximum est égale à la capacité minimum d’une coupe.

Algorithme de Ford-Fulkerson (EK)

L’algorithme le plus simple : tant qu’il existe un chemin augmentant dans le réseau résiduel (trouvé par BFS), on augmente le flot de la capacité minimale le long de ce chemin. Complexité : O(V · E²).

Algorithme de Dinic

Dinic améliore Ford-Fulkerson en construisent un graphe de niveau (BFS) puis en envoyant tous les flots possibles via DFS (qui utilise un pointeur courant pour éviter de reparcourir des arêtes inutiles). Complexité théorique : O(V² · E), mais beaucoup plus rapide en pratique.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5, M = 2e5 + 5;
const ll INF = 1e18;

struct Edge {
    int to, rev;
    ll cap;
};

vector<Edge> g[N];
int level[N], it[N];
int n, m, s, t;

void add_edge(int u, int v, ll c) {
    g[u].push_back({v, (int)g[v].size(), c});
    g[v].push_back({u, (int)g[u].size() - 1, 0});
}

bool bfs() {
    fill(level, level + n + 1, -1);
    queue<int> q;
    q.push(s);
    level[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& e : g[u]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[u] + 1;
                if (e.to == t) return true;
                q.push(e.to);
            }
        }
    }
    return false;
}

ll dfs(int u, ll flow) {
    if (u == t) return flow;
    for (int& i = it[u]; i < (int)g[u].size(); i++) {
        Edge& e = g[u][i];
        if (e.cap > 0 && level[e.to] == level[u] + 1) {
            ll pushed = dfs(e.to, min(flow, e.cap));
            if (pushed > 0) {
                e.cap -= pushed;
                g[e.to][e.rev].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

ll dinic() {
    ll flow = 0;
    while (bfs()) {
        fill(it, it + n + 1, 0);
        while (ll f = dfs(s, INF)) flow += f;
    }
    return flow;
}

Flot à coût minimum (Min-Cost Flow)

On cherche un flot de valeur maximale (ou une valeur donnée) en minimisant le coût total. Chaque arête a un coût unitaire. L’algorithme classique utilise un plus court chemin (SPFA ou Dijkstra avec potentiels) dans le réseau résiduel pour trouver un chemin augmentant de coût minimal, puis ajuste le flot.

struct Edge {
    int to, rev;
    ll cap, cost;
};

vector<Edge> g[N];
int n, m, s, t;
ll dist[N];
bool inq[N], vis[N];
int pv[N], pe[N];
const ll INF = 1e18;

void add_edge(int u, int v, ll cap, ll cost) {
    g[u].push_back({v, (int)g[v].size() , cap, cost});
    g[v].push_back({u, (int)g[u].size() - 1, 0, -cost});
}

bool spfa() {
    fill(dist, dist + n + 1, INF);
    fill(inq, inq + n + 1, false);
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (int i = 0; i < (int)g[u].size(); i++) {
            Edge& e = g[u][i];
            if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                dist[e.to] = dist[u] + e.cost;
                pv[e.to] = u;
                pe[e.to] = i;
                if (!inq[e.to]) {
                    inq[e.to] = true;
                    q.push(e.to);
                }
            }
        }
    }
    return dist[t] != INF;
}

pair<ll,ll> minCostMaxFlow() {
    ll flow = 0, cost = 0;
    while (spfa()) {
        ll aug = INF;
        for (int v = t; v != s; v = pv[v]) {
            int u = pv[v], i = pe[v];
            aug = min(aug, g[u][i].cap);
        }
        for (int v = t; v != s; v = pv[v]) {
            int u = pv[v], i = pe[v];
            g[u][i].cap -= aug;
            g[v][g[u][i].rev].cap += aug;
            cost += aug * g[u][i].cost;
        }
        flow += aug;
    }
    return {flow, cost};
}