Максимальный поток минимальной стоимости

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

class Edge {
    int _a, _b, capacity, flow, cost;
public:
    Edge(int a, int b, int capacity, int cost) : _a(a), _b(b), capacity(capacity), flow(0), cost(cost) {}
    int a() const {
        return _a;
    }
    int b() const {
        return _b;
    }
    int other(int v) const {
        return v == _a ? _b : _a;
    }
    int capacityTo(int v) const {
        return v == _b ? capacity - flow : flow;
    }
    int costTo(int v) const {
        return v == _b ? cost : -cost;
    }
    void addFlowTo(int v, int f) {
        flow += (v == _b ? f : -f);
    }
};

class Graph {
    vector<Edge> edges;
    vector<int> distTo;
    vector<int> edgeTo;
    void fordBellman(int v) {
        while (1) {
            bool update = 0;
            for (int i = 0; i < edges.size(); i++) {
                int a = edges[i].a(), b = edges[i].b();
                if (edges[i].capacityTo(b) && distTo[b] > distTo[a] + edges[i].costTo(b)) {
                    distTo[b] = distTo[a] + edges[i].costTo(b);
                    edgeTo[b] = i;
                    update = 1;
                }
                if (edges[i].capacityTo(a) && distTo[a] > distTo[b] + edges[i].costTo(a)) {
                    distTo[a] = distTo[b] + edges[i].costTo(a);
                    edgeTo[a] = i;
                    update = 1;
                }
            }
            if (!update)
                break;
        }
    }
    bool hasPath(int from, int to) {
        fill(distTo.begin(), distTo.end(), 1 << 30);
        distTo[from] = 0;
        fordBellman(from);
        return distTo[to] != 1 << 30;
    }
    int bottleneckCapacity(int from, int to) {
        int bCapacity = 1 << 30;
        for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
            bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
        return bCapacity;
    }
    long long addFlow(int from, int to, int flow) {
        long long deltaCost = 0;
        for (int v = to; v != from; v = edges[edgeTo[v]].other(v)) {
            edges[edgeTo[v]].addFlowTo(v, flow);
            deltaCost += flow * edges[edgeTo[v]].costTo(v);
        }
        return deltaCost;
    }
public:
    Graph(int verticesCount) {
        distTo.resize(verticesCount);
        edgeTo.resize(verticesCount);
    }
    void addEdge(int from, int to, int capacity, int cost) {
        edges.push_back(Edge(from, to, capacity, cost));
    }
    pair<long long, long long> minCostMaxFlow(int from, int to) {
        long long cost = 0, flow = 0;
        while (hasPath(from, to)) {
            int deltaFlow = bottleneckCapacity(from, to);
            cost += addFlow(from, to, deltaFlow);
            flow += deltaFlow;
        }
        return make_pair(cost, flow);
    }
};


int main() {
    int n;
    scanf("%d", &n);
    Graph g(2 * n + 2);

    int source = 0;
    for (int i = 1; i <= n; i++)
        g.addEdge(source, i, 1, 0);

    int c;
    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= 2 * n; j++) {
            scanf("%d", &c);
            g.addEdge(i, j, 1, c);
        }
    }

    int sink = 2 * n + 1;
    for (int i = n + 1; i <= 2 * n; i++)
        g.addEdge(i, sink, 1, 0);

    printf("%lld", g.minCostMaxFlow(source, sink).first);
}

Ссылки

Теория:

• e-maxx.ru — Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей
• neerc.ifmo.ru/wiki — Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости

Код:

• CodeLibrary — Maximum flow of minimum cost with Bellman–Ford
• CodeLibrary — Maximum flow of minimum cost with potentials for dense graphs
• CodeLibrary — Maximum flow of minimum cost with potentials
• Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Ford-Bellman algorithm as shortest path search method
• Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Dijkstra algorithm (with potentials) as shortest path search method. (Dijkstra for dense graphs running in O(N^2))
• Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Dijkstra algorithm (with potentials) as shortest path search method. (Dijkstra on heap for sparse graphs)

Задачи:

• Задачи: Максимальный поток минимальной стоимости