Алгоритм Форда-Фалкерсона

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    int a, b, cap, flow;
    Edge(int a, int b, int cap) : a(a), b(b), cap(cap), flow(0) {}
};
vector<Edge> edges;

int n, m, u[1010], INF = 1 << 30;
vector<int> g[1010];

int findPath(int v, int bottleneckFlow) {
    u[v] = 1;
    if (v == n - 1)
        return bottleneckFlow;
    for (int i = 0; i < g[v].size(); i++) {
       Edge &e = edges[g[v][i]], &re = edges[g[v][i] ^ 1];
       if (!u[e.b] && e.cap > e.flow) {
           int deltaFlow = findPath(e.b, min(bottleneckFlow, e.cap - e.flow));
           if (deltaFlow) {
               e.flow += deltaFlow;
               re.flow -= deltaFlow;
               return deltaFlow;
           }
       }
    }
    return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    int a, b, cap;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &cap);
        edges.push_back(Edge(a - 1, b - 1, cap));
        g[a - 1].push_back(edges.size() - 1);
        edges.push_back(Edge(b - 1, a - 1, cap));
        g[b - 1].push_back(edges.size() - 1);
    }
    
    int flow = 0;
    while (1) {
        fill(u, u + n, 0);
        int deltaFlow = findPath(0, INF);
        if (!deltaFlow)
            break;
        flow += deltaFlow;
    }
    printf("%d", flow);
}

Ссылки

• algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow
• neerc.ifmo.ru/wiki — Алгоритм Форда-Фалкерсона
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9
• CodeLibrary — Maximum flow. Ford-Fulkerson alogithm in O(V^2 * FLOW)
• Algos — Ford-Fulkerson maxflow
• VisuAlgo — Network Flow