maxFlow

1 import std.algorithm : equal;
2 import std.conv : to;
3 struct Edge {
4     int to, cap, rev;
5 }
6 void addEdge(Edge[][] g, int from, int to, int cap) {
7     g[from] ~= Edge(to, cap, g[to].length.to!int);
8     g[to] ~= Edge(from, 0, g[from].length.to!int-1);
9 }
10 
11 auto g = new Edge[][](4);
12 
13 addEdge(g, 0, 1, 3);
14 addEdge(g, 0, 2, 3);
15 addEdge(g, 1, 3, 2);
16 addEdge(g, 2, 3, 4);
17 auto res = maxFlow!(int, 0)(g, 0, 3);
18 assert(res.flow == 5);
19 //MinCut : S={0, 1}, T={2, 3}
20 assert(equal(res.dual, [false, false, true, true]));