Обсуждение:Алгоритм Форда-Фалкерсона

Старый код

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

struct Edge {
    int a, b, cap, flow;
    Edge(int a, int b, int cap, int flow) : a(a), b(b), cap(cap), flow(flow) {}
};
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, 0));
        g[a - 1].push_back(edges.size() - 1);
        edges.push_back(Edge(b - 1, a - 1, cap, 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);
}