最小費用流問題蟻本読書会

ひとりで勝手にはじめた蟻本読書会最大流問題と最小カット問題蟻本読書会の続きです。

最小費用流問題とは、流す量が与えられた際、流すために掛かる総費用を最小にするためにはどのようにするとよいのかを決定する問題です。

最小コストを調べる
そのパスに流せるだけ流す
辺の容量と逆辺の容量を更新する

与えられたフローに達するまで上記を繰り返すことで解を得ることができます。

F – 最小費用流

V 個の街があります。各街には 1, 2, …, V と番号が付いています。E 本の水道管があり、i 本目の水道管は街 u_i から街 v_i へ水を最大で c_i だけ流すことができますが、水を 1 流すごとに費用が d_i かかります。街 1 から街 V へ水を F だけ流すとき、合計費用の最小値を求めてください。

入力されるデータ
V E F
u_1 v_1 c_1 d_1
u_2 v_2 c_2 d_2
…
u_E v_E c_E d_E

（ただし、
1 ≦ V, E ≦ 100, 1 ≦ F ≦ 10^9
1 ≦ u_i, v_i ≦ V, 1 ≦ c_i, d_i ≦ 10^9 ）

最大流問題と同じように逆辺をつくります。そして逆辺のコストは辺のコストの符号を反転させたものにします。頂点 A から頂点 B へ容量 c、コスト d の辺を張ったら、頂点 B から頂点 A へ容量 0、コスト -d の逆辺を張ります。それから問題文には「多重辺は存在しない」とは書いていません。何度やっても WA（wrong answer）が 2 件でるのでおかしいと思っていたら「多重辺は存在しない」という勝手な前提でコードを書いていた鳩のミスでした。

Edgeクラスを定義するときに逆辺がすぐに取得できるように Reverse というプロパティを定義しています。

またコストが負数の辺が存在するのでダイクストラ法が使えません。ここではベルマンフォード法でコストが最小になる経路を求めています。負閉路のチェックもしていますが、実際に負閉路ができることはないみたいです。

using System;
using System.Collections.Generic;
using System.Data.SqlTypes;
using System.Linq;

class Edge
{
    public Edge(int from, int next, long cost, long capacity)
    {
        From = from;
        Next = next;
        Cost = cost;
        Capacity = capacity;
    }

    public int From { get; }
    public int Next { get; }
    public long Cost { get; }
    public long Capacity { set; get; }
    public Edge Reverse { set; get; };
}

class Program
{
    static void Main()
    {
        int V, E; long F;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            V = vs[0];
            E = vs[1];
            F = vs[2];
        }

        List<Edge>[] list = new List<Edge>[V];
        for (int i = 0; i < V; i++)
            list[i] = new List<Edge>();

        for (int i = 0; i < E; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = vs[0] - 1;
            int v = vs[1] - 1;
            int c = vs[2];
            int d = vs[3];
            Edge edge1 = new Edge(u, v, d, c);
            Edge edge2 = new Edge(v, u, -d, 0); // 逆辺
            list[u].Add(edge1);
            list[v].Add(edge2);
            edge1.Reverse = edge2; // 相互に逆辺がすぐに取得できるようにする
            edge2.Reverse = edge1;
        }

        long total = 0;
        while (true)
        {
            FlowCost flowCost = BellmanFord(list, V, 0, V - 1, F);
            if (flowCost == null)
                break;

            F -= flowCost.Flow; // フローを流したら残りを計算する
            total += flowCost.Cost; // フローを流すためのコストを加算する
            if (F <= 0) // 流すべきフローを流し終わったら終了
                break;
        }
        if(F == 0)
            Console.WriteLine(total); // 流すべきフローを流すことができた
        else
            Console.WriteLine(0); // 流すべきフローを流すことができなかった
    }

    static FlowCost BellmanFord(List<Edge>[] edgelist, int V, int start, int goal, long maxFlow)
    {
        Edge[] froms = new Edge[V];
        long[] costs = new long[V];

        long inf = long.MaxValue / 10;
        for (int i = 0; i < V; i++)
            costs[i] = inf;

        costs[start] = 0;

        // ループは N - 1 回回せばよいが負閉路を検出するため1回余分に回す
        bool updated = false;
        for (int count = 0; count < V; count++)
        {
            updated = false;
            for (int from = 0; from < V; from++)
            {
                long oldCost = costs[from];
                var edges = edgelist[from];

                foreach (Edge edge in edges)
                {
                    if (edge.Capacity <= 0)
                        continue;

                    if (costs[edge.Next] > oldCost + edge.Cost)
                    {
                        costs[edge.Next] = oldCost + edge.Cost;
                        froms[edge.Next] = edge;
                        updated = true;
                    }
                }
            }
            if (!updated) // これ以上更新されることはない（やるだけ無駄）
                break;
        }

        // N回 ループを回しても updated == true になるということは永久に更新される
        // つまり負閉路が存在するのだがテストケースでは存在しない
        if (updated)
        {
            Console.WriteLine("負閉路");
            return null;
        }

        // 終点までたどり着ける場合は流せるフローを計算して流す
        if (costs[goal] < inf)
        {
            Edge last = froms[goal];
            List<Edge> list = new List<Edge>(); // 始点から終点までに経由する辺のリスト
            list.Add(last);

            while (true)
            {
                last = froms[last.From];
                if(last == null)
                    break;

                list.Add(last);
            }

            // 辺の容量の最小値が流すことができるフロー
            long flow = Math.Min(maxFlow, list.Min(_ => _.Capacity));

            long cost = 0;
            foreach (Edge edge in list)
            {
                edge.Capacity -= flow;
                edge.Reverse.Capacity += flow; // 逆辺
                cost += flow * edge.Cost;  // フローを流すためのコストを計算する
            }
            return new FlowCost(flow, cost); // 流したフローとコストをセットにして返す
        }
        else
            return null;
    }
}

class FlowCost
{
    public FlowCost(long flow, long cost)
    {
        Cost = cost;
        Flow = flow;
    }

    public long Cost { get; }
    public long Flow { get; }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

using System;

using System.Collections.Generic;

using System.Data.SqlTypes;

using System.Linq;

class Edge

{

public Edge(int from, int next, long cost, long capacity)

{

From = from;

Next = next;

Cost = cost;

Capacity = capacity;

}

public int From { get; }

public int Next { get; }

public long Cost { get; }

public long Capacity { set; get; }

public Edge Reverse { set; get; };

}

class Program

{

static void Main()

{

int V, E; long F;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

V = vs[0];

E = vs[1];

F = vs[2];

}

List<Edge>[] list = new List<Edge>[V];

for (int i = 0; i < V; i++)

list[i] = new List<Edge>();

for (int i = 0; i < E; i++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = vs[0] - 1;

int v = vs[1] - 1;

int c = vs[2];

int d = vs[3];

Edge edge1 = new Edge(u, v, d, c);

Edge edge2 = new Edge(v, u, -d, 0); // 逆辺

list[u].Add(edge1);

list[v].Add(edge2);

edge1.Reverse = edge2; // 相互に逆辺がすぐに取得できるようにする

edge2.Reverse = edge1;

}

long total = 0;

while (true)

{

FlowCost flowCost = BellmanFord(list, V, 0, V - 1, F);

if (flowCost == null)

break;

F -= flowCost.Flow; // フローを流したら残りを計算する

total += flowCost.Cost; // フローを流すためのコストを加算する

if (F <= 0) // 流すべきフローを流し終わったら終了

break;

}

if(F == 0)

Console.WriteLine(total); // 流すべきフローを流すことができた

else

Console.WriteLine(0); // 流すべきフローを流すことができなかった

}

static FlowCost BellmanFord(List<Edge>[] edgelist, int V, int start, int goal, long maxFlow)

{

Edge[] froms = new Edge[V];

long[] costs = new long[V];

long inf = long.MaxValue / 10;

for (int i = 0; i < V; i++)

costs[i] = inf;

costs[start] = 0;

// ループは N - 1 回回せばよいが負閉路を検出するため1回余分に回す

bool updated = false;

for (int count = 0; count < V; count++)

{

updated = false;

for (int from = 0; from < V; from++)

{

long oldCost = costs[from];

var edges = edgelist[from];

foreach (Edge edge in edges)

{

if (edge.Capacity <= 0)

continue;

if (costs[edge.Next] > oldCost + edge.Cost)

{

costs[edge.Next] = oldCost + edge.Cost;

froms[edge.Next] = edge;

updated = true;

}

if (!updated) // これ以上更新されることはない（やるだけ無駄）

break;

}

// N回ループを回しても updated == true になるということは永久に更新される

// つまり負閉路が存在するのだがテストケースでは存在しない

if (updated)

{

Console.WriteLine("負閉路");

return null;

}

// 終点までたどり着ける場合は流せるフローを計算して流す

if (costs[goal] < inf)

{

Edge last = froms[goal];

List<Edge> list = new List<Edge>(); // 始点から終点までに経由する辺のリスト

list.Add(last);

while (true)

{

last = froms[last.From];

if(last == null)

break;

list.Add(last);

}

// 辺の容量の最小値が流すことができるフロー

long flow = Math.Min(maxFlow, list.Min(_ => _.Capacity));

long cost = 0;

foreach (Edge edge in list)

{

edge.Capacity -= flow;

edge.Reverse.Capacity += flow; // 逆辺

cost += flow * edge.Cost; // フローを流すためのコストを計算する

}

return new FlowCost(flow, cost); // 流したフローとコストをセットにして返す

}

else

return null;

}

class FlowCost

{

public FlowCost(long flow, long cost)

{

Cost = cost;

Flow = flow;

}

public long Cost { get; }

public long Flow { get; }

}

最小費用流問題蟻本読書会

F – 最小費用流

関連記事

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ