dunkelheit reference

dkh.graph.mincostflow

  • MinCostFlowInfo

    Declaration

    struct MinCostFlowInfo(C, D, D EPS, T);

    最小費用流の情報

    • capFlow

      Declaration

      C capFlow;

      今の最短路の容量, 今流した量

    • flow

      Declaration

      D flow;

      今の最短路の長さ, 今流したコスト

    • dual

      Declaration

      D[] dual;

      双対問題の答え(=ポテンシャル)

  • minCostFlow

    Declaration

    MinCostFlowInfo!(C, D, EPS, T) minCostFlow(C, D, D EPS, T)(T g, int s, int t, bool neg = false);

    最小費用流

    Examples

    1. 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);

  • singleFlow

    Declaration

    C singleFlow(C, D, alias EPS, T)(ref MinCostFlowInfo!(C, D, EPS, T) mcfInfo, C c);

    min(nc, c)流す

  • manyFlow

    Declaration

    void manyFlow(C, D, alias EPS, T)(ref MinCostFlowInfo!(C, D, EPS, T) mcfInfo, C c);

    流量がcになるまで流せるだけ流し続ける