Le problème de flot maximal consiste à déterminer la quantité maximale de flux pouvant être acheminée d'une source à un puits dans un réseau. Deux algorithmes courants sont l'algorithme EK (Edmonds-Karp) et l'algorithme Dinic, tous deux basés sur la recherche de chemins aumgentants.

Algorithme EK (Edmonds-Karp)

L'algorithme EK utilise une recherche en largeur (BFS) pour trouver des chemins augmentants de la source au puits. À chaque itération, il identifie un chemin avec une capacité résiduelle positive et met à jour les flux en conséquence.

#include <iostream>
#include <queue>
#include <cstring>
#define MAXN 1000001
#define INF 2147483647
using namespace std;

int compteur = 1, premier[MAXN];
int dist[MAXN], visite[MAXN], flot[MAXN], precedent[MAXN], flotMax;
struct Arc {
    int origine, destination, capacite, suivant;
} arc[MAXN];
queue<int> file;
int source, puits, n, m;

inline int lireEntier() {
    int x = 0;
    bool positif = true;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') positif = false;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c - '0');
    return positif ? x : -x;
}

inline void ajouterArc(int u, int v, int cap) {
    compteur++;
    arc[compteur].origine = u;
    arc[compteur].destination = v;
    arc[compteur].capacite = cap;
    arc[compteur].suivant = premier[u];
    premier[u] = compteur;
}

inline bool bfsEK() {
    memset(precedent, 0, sizeof(precedent));
    memset(visite, -1, sizeof(visite));
    file.push(source);
    visite[source] = 0;
    dist[source] = 0;
    flot[source] = INF;
    while (!file.empty()) {
        int noeud = file.front();
        file.pop();
        visite[noeud] = 1;
        for (int i = premier[noeud]; i != -1; i = arc[i].suivant) {
            int voisin = arc[i].destination;
            if (arc[i].capacite > 0 && visite[voisin] == -1) {
                flot[voisin] = min(flot[noeud], arc[i].capacite);
                precedent[voisin] = i;
                file.push(voisin);
                visite[voisin] = 0;
            }
        }
    }
    return visite[puits] != -1;
}

inline void mettreAJour() {
    int courant = puits;
    while (courant != source) {
        int idx = precedent[courant];
        arc[idx].capacite -= flot[puits];
        arc[idx ^ 1].capacite += flot[puits];
        courant = arc[idx].origine;
    }
    flotMax += flot[puits];
}

inline void executerEK() {
    flotMax = 0;
    while (bfsEK()) {
        mettreAJour();
    }
}

int main() {
    memset(premier, -1, sizeof(premier));
    n = lireEntier(); m = lireEntier(); source = lireEntier(); puits = lireEntier();
    for (int i = 0; i < m; i++) {
        int u = lireEntier(), v = lireEntier(), cap = lireEntier();
        ajouterArc(u, v, cap);
        ajouterArc(v, u, 0);
    }
    executerEK();
    printf("%d", flotMax);
    return 0;
}

Algorithme Dinic

L'algorithme Dinic améliore EK en utilisant une structure de niveaux pour guider la recherche en profondeur (DFS). Il commence par une BFS pour attribuer des niveaux aux nœuds, puis effectue des DFS pour envoyer du flux le long des chemins augmentants avec des niveaux croissants.

#include <iostream>
#include <queue>
#include <cstring>
#define MAXN 1000001
#define INF 2147483647
using namespace std;

int compteur = 1, premier[MAXN], niveau[MAXN];
struct Arc {
    int origine, destination, capacite, suivant;
} arc[MAXN];
queue<int> file;
int source, puits, n, m;

inline int lireEntier() {
    int x = 0;
    bool positif = true;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') positif = false;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c - '0');
    return positif ? x : -x;
}

inline void ecrireEntier(int x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) ecrireEntier(x / 10);
    putchar(x % 10 + '0');
}

inline void ajouterArc(int u, int v, int cap) {
    compteur++;
    arc[compteur].origine = u;
    arc[compteur].destination = v;
    arc[compteur].capacite = cap;
    arc[compteur].suivant = premier[u];
    premier[u] = compteur;
}

inline bool bfsDinic() {
    memset(niveau, -1, sizeof(niveau));
    niveau[source] = 0;
    file.push(source);
    while (!file.empty()) {
        int noeud = file.front();
        file.pop();
        for (int i = premier[noeud]; i != -1; i = arc[i].suivant) {
            int voisin = arc[i].destination;
            if (arc[i].capacite > 0 && niveau[voisin] == -1) {
                niveau[voisin] = niveau[noeud] + 1;
                file.push(voisin);
            }
        }
    }
    return niveau[puits] != -1;
}

inline int dfsDinic(int noeud, int flotDisponible) {
    if (noeud == puits) return flotDisponible;
    int flotEnvoye = 0;
    for (int i = premier[noeud]; i != -1 && flotDisponible > 0; i = arc[i].suivant) {
        int voisin = arc[i].destination;
        if (arc[i].capacite > 0 && niveau[voisin] == niveau[noeud] + 1) {
            int minCap = min(arc[i].capacite, flotDisponible);
            int flot = dfsDinic(voisin, minCap);
            if (flot > 0) {
                arc[i].capacite -= flot;
                arc[i ^ 1].capacite += flot;
                flotDisponible -= flot;
                flotEnvoye += flot;
            }
        }
    }
    return flotEnvoye;
}

inline int executerDinic() {
    int flotTotal = 0;
    while (bfsDinic()) {
        flotTotal += dfsDinic(source, INF);
    }
    return flotTotal;
}

int main() {
    memset(premier, -1, sizeof(premier));
    n = lireEntier(); m = lireEntier(); source = lireEntier(); puits = lireEntier();
    for (int i = 0; i < m; i++) {
        int u = lireEntier(), v = lireEntier(), cap = lireEntier();
        ajouterArc(u, v, cap);
        ajouterArc(v, u, 0);
    }
    int resultat = executerDinic();
    ecrireEntier(resultat);
    return 0;
}