dunkelheit reference

dkh.graph.maxflow

  • MaxFlowInfo

    Declaration

    struct MaxFlowInfo(C);

    maxflowの情報

    • flow

      Declaration

      C flow;

      流量

    • dual

      Declaration

      bool[] dual;

      最小カット(S側:false, T側:true)

  • maxFlow

    Declaration

    MaxFlowInfo!C maxFlow(C, C EPS, T)(T g, size_t s, size_t t, C gap = C.max);

    MaxFlow(Dinic)

    Parameters

    T g

    graph

    size_t s

    source node

    size_t t

    sink node

    C gap

    maximum flow

    Examples

    1. import std.algorithm : equal; import std.conv : to; struct Edge { int to, cap, rev; } void addEdge(Edge[][] g, int from, int to, int cap) { g[from] ~= Edge(to, cap, g[to].length.to!int); g[to] ~= Edge(from, 0, g[from].length.to!int-1); } auto g = new Edge[][](4); addEdge(g, 0, 1, 3); addEdge(g, 0, 2, 3); addEdge(g, 1, 3, 2); addEdge(g, 2, 3, 4); auto res = maxFlow!(int, 0)(g, 0, 3); assert(res.flow == 5); //MinCut : S={0, 1}, T={2, 3} assert(equal(res.dual, [false, false, true, true]));