Алгоритм Диница

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
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) {}
    int other(int v) {
        return v == a ? b : a;
    }
    int capTo(int v) {
        return v == b ? cap - flow : flow;
    }
    void addFlowTo(int v, int f) {
        flow += (v == b ? f : -f);
    }
};
vector<Edge> edges;

int n, m, u[1010], p[1010], pos[1010];
vector<int> g[1010];

bool bfs(int v, int vTarget) {
    queue<int> q;
    u[v] = 1;
    q.push(v);
    while (!q.empty()) {
        v = q.front();
        q.pop();
        if (v == vTarget)
            return 1;
        for (int i = 0; i < g[v].size(); i++) {
            int e = g[v][i], to = edges[e].other(v);
            if (!u[to] && edges[e].capTo(to)) {
                p[to] = e;
                u[to] = u[v] + 1;
                q.push(to);
            }
        }
    }
    return 0;
}

bool dfs(int v, int vTarget) {
    if (v == vTarget)
        return 1;
    for (; pos[v] < g[v].size(); pos[v]++) {
        int e = g[v][pos[v]], to = edges[e].other(v);
        if (u[v] + 1 == u[to] && edges[e].capTo(to)) {
            p[to] = e;
            if (dfs(to, vTarget))
                return 1;
        }
    }
    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);
        g[b - 1].push_back(edges.size() - 1);
    }

    int flow = 0;
    while (1) {
        fill(u, u + n, 0);
        if (!bfs(0, n - 1))
            break;
        fill(pos, pos + n, 0);
        while (dfs(0, n - 1)) {
            int deltaFlow = 1 << 30;
            for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
                deltaFlow = min(deltaFlow, edges[p[v]].capTo(v));
            flow += deltaFlow;
            for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
                edges[p[v]].addFlowTo(v, deltaFlow);
        }
    }
    printf("%d", flow);
}

Ссылки