minCostFlow

1 import std.conv : to;
2 struct Edge {
3     int to, cap, dist, rev;
4 }
5 
6 void addEdge(Edge[][] g, int from, int to, int cap, int dist) {
7     g[from] ~= Edge(to, cap, dist, g[to].length.to!int);
8     g[to] ~= Edge(from, 0, -dist, g[from].length.to!int-1);
9 }
10 
11 auto g = new Edge[][](4);
12 
13 addEdge(g, 0, 1, 10, 3);
14 addEdge(g, 0, 2, 12, 3);
15 addEdge(g, 1, 3, 3, 2);
16 addEdge(g, 2, 3, 20, 4);
17 
18 auto mcfInfo = minCostFlow!(int, int, 0)(g, 0, 3, false);
19 //最初は 0->1->3で容量3, 距離5を流せる
20 assert(mcfInfo.nc == 3 && mcfInfo.nd == 5);
21 
22 //最短経路が変わらない間(=容量3)流す
23 mcfInfo.singleFlow(10^^9);
24 
25 assert(mcfInfo.capFlow == 3 && mcfInfo.flow == 15);
26 
27 //次は 0->2->3で容量12, 距離7を流せる
28 assert(mcfInfo.nc == 12 && mcfInfo.nd == 7);
29 
30 //最短経路が変わらない間(=容量12)流す
31 mcfInfo.singleFlow(10^^9);
32 
33 assert(mcfInfo.capFlow == 3 + 12);
34 assert(mcfInfo.flow == 15 + 12*7);