minCostFlow

import std.conv : to;
struct Edge {
    int to, cap, dist, rev;
}

void addEdge(Edge[][] g, int from, int to, int cap, int dist) {
    g[from] ~= Edge(to, cap, dist, g[to].length.to!int);
    g[to] ~= Edge(from, 0, -dist, g[from].length.to!int-1);
}

auto g = new Edge[][](4);

addEdge(g, 0, 1, 10, 3);
addEdge(g, 0, 2, 12, 3);
addEdge(g, 1, 3, 3, 2);
addEdge(g, 2, 3, 20, 4);

auto mcfInfo = minCostFlow!(int, int, 0)(g, 0, 3, false);
//最初は 0->1->3で容量3, 距離5を流せる
assert(mcfInfo.nc == 3 && mcfInfo.nd == 5);

//最短経路が変わらない間(=容量3)流す
mcfInfo.singleFlow(10^^9);

assert(mcfInfo.capFlow == 3 && mcfInfo.flow == 15);

//次は 0->2->3で容量12, 距離7を流せる
assert(mcfInfo.nc == 12 && mcfInfo.nd == 7);

//最短経路が変わらない間(=容量12)流す
mcfInfo.singleFlow(10^^9);

assert(mcfInfo.capFlow == 3 + 12);
assert(mcfInfo.flow == 15 + 12*7);