AtCoder NoviStepsを埋めてみる(32) 燃やす埋める問題がおもしろすぎたの続きです。今回は最小費用流問題です。
最小費用流問題とは？
最小費用流問題とは、フローを流す量が与えられている場合、流すために掛かる総費用を最小にするためにはどのようにするとよいのかを決定する問題です。
ac-library-csharp というライブラリには McfGraph<T> クラスがあり、これを使えば簡単に最小費用流問題を解くことができます。ところがこのライブラリはコストに負の値を設定することができません（負のコストを設定すると例外が発生する）。なので、自分で実装することにします。
やることは、
始点から終点まで流せるパスでコストが最小であるものを取得する
そのパスに流せるだけ流す
辺の容量と逆辺の容量を更新する
与えられたフローに達するまで上記を繰り返す
です。
ただし注意しなければならないことがあります。単純に流せる量を記録しておくだけでは不十分です。以下の図のような場合を考えます。矢印があるところに書かれているのはコストではなく容量です。
これなら考えるまでもなく、答えは35です。0 → 1 → 3 と 20 流すことができて、そのあと 0 → 2 → 3 と 15 流すことができます。あわせて 35 が答えです。
ところが最初に 0 → 1 → 2 → 3 を選択してしまうと、このパスに 10 を流すことができるので、以下のように更新されることになります。
そのあと 0 → 1 → 3 と 10 流すことになります。すると以下のように更新されます。
さらに 0 → 2 → 3 と 5 流すことができるので流してみることにします。
これ以上流すことができないので 10 + 10 + 5 で 25 が答え・・・。あれ？ おかしいですね。
逆辺とは？
このような問題を回避するために逆辺を定義します。逆辺とは逆向きの 容量 0 の辺のことです。
最初に 0 → 1 → 2 → 3 を選択した場合、以下のように更新されます。フローを流すと逆辺の容量は増えます。
次に 0 → 2 → 1 → 3 を選択した場合は、10 流すことができて以下のように更新されます。
次に 0 → 1 → 2 → 3 を選択した場合は、5 流すことができて以下のように更新されます。
次に 0 → 2 → 1 → 3 を選択した場合は、5 流すことができて以下のように更新されます。
次に 0 → 1 → 3 を選択した場合は、5 流すことができて以下のように更新されます。
これ以上は流すことはできません。全部足すと 10 + 10 + 5 + 5 + 5 = 35 となり正解と一致しています。
MinCostFlowNegative クラスの実装
負のコストも設定できるようにMinCostFlowNegative クラスを定義します。
まず内部の処理で辺の状態を管理するために InternalEdge クラスを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class MinCostFlowNegative { class InternalEdge { public int To; // どの頂点へ public long InitCap; // 初期状態の辺の容量 public long Cap; // あとどれだけ流せるか？ public long Cost; // 流量 1 を流すためのコスト public InternalEdge Reverse = null; // 自分自身の逆辺 public bool IsReverse = false; // これは逆辺かどうか？ public InternalEdge(int to, long cap, long cost, bool isReverse) { To = to; Cap = InitCap = cap; Cost = cost; IsReverse = isReverse; } } } |
コンストラクタを示します。頂点数をフィールド変数に保存し、InternalEdge を格納するためのリストを初期化します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class MinCostFlowNegative { private int N; private List<InternalEdge>[] G; public MinCostFlowNegative(int n) { N = n; G = new List<InternalEdge>[n]; for (int i = 0; i < n; i++) G[i] = new List<InternalEdge>(); } } |
辺を追加する処理を示します。辺オブジェクトを生成して互いの逆辺がわかるようにしています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class MinCostFlowNegative { public void AddEdge(int from, int to, long cap, long cost) { InternalEdge edge = new InternalEdge(to, cap, cost, false); InternalEdge r_edge = new InternalEdge(from, 0, -cost, true); edge.Reverse = r_edge; r_edge.Reverse = edge; G[from].Add(edge); G[to].Add(r_edge); } } |
始点から終点にむけてフローを流すためにもっともコストが低いパスを探す処理を示します。戻り値は始点から終点まで移動するのに通らなければならない辺のリストと最小コストです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
public class MinCostFlowNegative { (long, List<InternalEdge>) Bfs(int s, int t) { Queue<int> q = new Queue<int>(); const long INF = long.MaxValue; InternalEdge[] froms = new InternalEdge[N]; long[] dists = new long[N]; Array.Fill(dists, INF); dists[s] = 0; q.Enqueue(s); while (q.Count > 0) { int cur = q.Dequeue(); foreach (var edge in G[cur]) { if (edge.Cap <= 0) continue; if (dists[edge.To] > dists[cur] + edge.Cost) { dists[edge.To] = dists[cur] + edge.Cost; froms[edge.To] = edge; q.Enqueue(edge.To); } } } if (dists[t] == INF) return (INF, new List<InternalEdge>()); int last_v = t; List<InternalEdge> uses = new List<InternalEdge>(); while (last_v != s) { InternalEdge last_e = froms[last_v]; InternalEdge last_r = last_e.Reverse; last_v = last_r.To; uses.Add(last_e); } return (dists[t], uses); } } |
s → t に最大で maxFlow 流したときの最小費用流を求める処理を示します。
ここでは
始点から終点まで流せるパスでコストが最小であるものを取得する
そのパスに流せるだけ流す
辺の容量と逆辺の容量を更新する
与えられたフローに達するまで上記を繰り返す
を実行しています。
戻り値は実際に流すことができた流量と最小費用です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class MinCostFlowNegative { public (long Flow, long Cost) Flow(int s, int t, long maxFlow) { long flow = 0; // 実際に流すことができた流量 long cost = 0; // コストの総和 while (flow < maxFlow) { // コスト最小で終点までたどり着けるパスを探す var res = Bfs(s, t); // パスが存在しない場合はこれ以上流せないので終了 if (res.Item2.Count == 0) break; // 発見したパス上の残容量の最小値が実際に流せる量（maxFlow - flow を超えないように注意） long addFlow = Math.Min(res.Item2.Min(_ => _.Cap), maxFlow - flow); // 実際に流して辺と逆辺の残容量を更新する foreach (var use in res.Item2) { use.Cap -= addFlow; use.Reverse.Cap += addFlow; } // 実際に流せた量とコストを更新 flow += addFlow; cost += addFlow * res.Item1; } return (flow, cost); } } |
最小費用流を求めたあと、各辺にじっさいにどれだけ流すことができたのかを取得する処理を示します。
逆辺でない辺について、初期状態の容量と残容量を比較すればどれだけ流すことができたかわかるので、それを返すことにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class MinCostFlowNegative { public class Edge { public int From; public int To; public long Flow; public long Cost; public Edge(int from, int to, long flow, long cost) { From = from; To = to; Flow = flow; Cost = cost; } } public List<Edge> GetEdges() { List<Edge> res = new List<Edge>(); for (int from = 0; from < N; from++) { foreach (var edge in G[from]) { if (!edge.IsReverse) res.Add(new Edge(from, edge.To, edge.InitCap - edge.Cap, edge.Cost)); } } return res; } } |
F – 最小費用流
ためしに問題を解いてみることにします。
問題の概要
V 個の街と E 本の水道管がある。
i 本目の水道管は街 u[i] から街 v[i] へ水を最大で c[i] だけ流すことができるが、水を 1 流すごとに費用が d[i] かかる。
街 1 から街 V へ水を F だけ流すとき、合計費用の最小値を求めよ。
そのまんまの最小費用流問題です。この問題には負のコストはありませんが、一応自作クラスでも普通に AC できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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]; } var G = new MinCostFlowNegative(V); 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]; G.AddEdge(u, v, c, d); } var res = G.Flow(0, V - 1, F); if (F == res.Flow) Console.WriteLine(res.Cost); else Console.WriteLine(0); } } |
C – Moving Pieces
問題の概要
N 行 M 列からなる盤面がある。
マスの文字が ‘.’ であれば空マス、’#’ であれば障害物が置かれているマス、’o’ であれば駒が置かれているマスである。
駒を 1 つ選び 1 個下、もしくは 1 個右のマスに移動させる。
ただし他の駒もしくは障害物のあるマスに駒を移動させる操作はできない。
いうまでもなく駒が盤面を飛び出すような操作もできない。できるだけ多くの回数操作をしたいと考えている。操作回数の最大値を求めよ。
この問題は工夫すれば非負数のコストを設定することで解くことができますが、テストも兼ねて負のコストを設定して解いてみることにします。
まず超頂点 S から ‘o’ があるマスへ容量 1、コスト 0 の辺を張ります。つぎに ‘#’ ではないすべてのマスから超頂点 T へ容量 1、コスト 0 の辺を張ります。そして ‘#’ ではないすべてのマスからその右側と下側にあるマスがそれぞれ ‘#’ でないならそれぞれ容量 ∞、コスト -1 の辺を張ります。これで最大流量を ‘o’ の個数にして S から T への最小費用流を求めると、最小費用の符号を反転させたものが最大の移動回数となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Program { static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int H, int W) = (hw[0], hw[1]); char[,] grid = new char[H, W]; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) grid[r, c] = vs[c]; } MinCostFlowNegative G = new MinCostFlowNegative(H * W + 2); int s = H * W; int t = H * W + 1; int cnt = 0; // o の個数 for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r, c] == 'o') { cnt++; G.AddEdge(s, r * W + c, 1, 0); } if (grid[r, c] != '#') { if (c + 1 < W && grid[r, c + 1] != '#') G.AddEdge(r * W + c, r * W + c + 1, int.MaxValue, -1); if (r + 1 < H && grid[r + 1, c] != '#') G.AddEdge(r * W + c, (r + 1) * W + c, int.MaxValue, -1); G.AddEdge(r * W + c, t, 1, 0); } } } var res = G.Flow(s, t, cnt); Console.WriteLine(-res.Cost); } } |
