ひとりで勝手にはじめた蟻本読書会 繰り返し2乗法と行列累乗 フィボナッチ数列 の続きです。
最大流問題を解く
各地点が水道管でつながっていて、ある地点から別の地点へ一定量の水を流し続けることを考えます。始点と終点以外では、各地点に入ってくる水の量と出ていく水の量は同じです。このような条件下では流れる水は分岐や合流を繰り返し、いくつかの経路をたどって終点まで到着します。この水の流れのことをフローと呼びます。
水道管に流せる水の量に上限があるように、各辺に流すことのできる最大の量 (容量) には制限があります。このような制約下で、どれだけ大きい流量のフローを流せるかを考えるのが最大流問題です。
では、どのようにして解を求めればよいのでしょうか？ まずは始点から終点に向け水を流せる経路を探します。見つかったら水を流し、使用する水道管の容量をそのぶん減らす・・・という方法でうまくいくでしょうか？
実はこの方法ではフローの最大値を取得できない場合があります。そこで鍵となるのが逆辺です。逆辺の基本的な考え方は「フローが流れている辺には逆向きにフローを流し戻すことができる」です。
ある辺にフローを流す場合は、その辺の容量を流した分だけ減らして、その逆向きの辺の容量を流した分だけ増やします。こうすることで最大流を正しく求めることができます。このようなアルゴリズムを Ford-Fulkerson 法と呼びます。
E – 最大流
V個の街があります。各街には 1, 2, …, V と番号が付いています。E 本の水道管があり、i 本目の水道管は街 u_i から街 v_i へ水を最大で c_i だけ流すことが出来ます。街 1 から街 V へ流せる水の量の最大値を求めてください。
入力されるデータ
V E
u_1 v_1 c_1
u_2 v_2 c_2
…
u_E v_E c_E
（ただし、1 ≦ V, E ≦ 100, 1 ≦ c_i ≦ 10^9 ）
入力されたデータから隣接行列をつくり、幅優先探索でフローを流せる経路を探します。見つかったらどれだけのフローを流せるかを調べます。流すことができるのは経由する辺の容量の最小値です。流せる量が取得できたらその辺の容量を流した分だけ減らし、逆辺の容量をその分増やします。
この処理を流せる経路が見つからなくなるまで繰り返します。
|
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int V, E; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); V = vs[0]; E = vs[1]; } // 隣接行列をつくる long[,] mat = new long[V, V]; for (int i = 0; i < E; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; mat[a, b] = c; } long total = 0; while (true) { long add = BFS(mat, V, 0, V - 1); total += add; if (add == 0) break; } Console.WriteLine(total); } // 幅優先探索で start から goal までフローを流せる経路を探す // 見つかったらその辺の容量を流した分だけ減らし、逆辺の容量をその分増やす // 戻り値として流したフローを返す static long BFS(long[,] mat, int V, int start, int goal) { bool[] visits = new bool[V]; int[] froms = new int[V]; Queue<int> q = new Queue<int>(); q.Enqueue(start); visits[start] = true; while (q.Count > 0) { int cur = q.Dequeue(); for (int i = 0; i < mat.GetLength(0); i++) { if (mat[cur, i] > 0) { if (visits[i]) continue; visits[i] = true; froms[i] = cur; q.Enqueue(i); } } } if (visits[goal]) { int last = goal; List<int> list = new List<int>(); list.Add(last); while (last != start) { int from = froms[last]; last = from; list.Add(last); } list.Reverse(); long min = long.MaxValue; for (int i = 0; i < list.Count - 1; i++) { int from = list[i]; int to = list[i + 1]; min = Math.Min(min, mat[from, to]); } for (int i = 0; i < list.Count - 1; i++) { int from = list[i]; int to = list[i + 1]; mat[from, to] -= min; mat[to, from] += min; } return min; } else return 0; } } |
最大フロー最小カット定理
グラフ理論において、グラフの頂点の 2 分割 (S, T) をカットとよびます。また分割された S と T にそれぞれ頂点 u と v が存在する場合、u, v をつなぐ辺をカットエッジと呼びます。
カットの重みは、カットエッジの総数 (それぞれの辺重みの総和) で表されます。これが最小になるカットのことを最小カットといいます。そして最大フローと最小カットの重みは同じです（最大フロー最小カット定理）。
G – Builder Takahashi
N 頂点 M 辺の単純連結無向グラフがあります。頂点には頂点 1, 頂点 2, …, 頂点 N と番号が振られています。辺には 辺 1, 辺 2, …, 辺 M と番号が振られています。辺 i は頂点 a_i と頂点 b_i を双方向に結んでいます。また、頂点 1 と頂点 N を直接結ぶ辺は存在しません。
各頂点の状態は「何もない頂点」か「壁がある頂点」のいずれかです。はじめ、全ての頂点は何もない頂点です。
青木君は頂点 1 を出発して、グラフ上を辺に沿って移動して頂点 N へ行こうとしています。ただし、壁がある頂点への移動を行うことはできません。
高橋君は、青木君が移動を開始する前にいくつかの頂点を選んで壁を建てることで、青木君がどのように移動しても頂点 N へ行くことができないようにすることにしました。
高橋君が頂点 i に壁を建てるには c_i 円を払う必要があります。また、頂点 1 および頂点 N には壁を建てられません。
高橋君が条件を満たすように壁を建てるときに最小で何円払う必要があるでしょうか。また、その時の壁の立て方を 1 つ出力してください。
入力されるデータ
N M
a_1 b_1
a_2 b_2
…
a_M b_M
c_1 c_2 … c_N（ただし、
3 ≦ N ≦ 100
1 ≦ a_i, b_i ≦ N
1 ≦ c_i ≦ 10^9 ）
全体を壁で2分割する、壁を建てる部分がカットエッジとなり、その容量を最小にする。つまりこれは最小カット問題です。壁を辺ではなく頂点の内部につくる場合は頂点を IN と OUT の 2 つにわけます。そして IN と OUT を辺でつなぎ、その容量を c_i とします。また頂点 a と b が相互に移動可能であるなら a の OUT と b の IN、b の OUT と a の IN を容量 ∞ の辺でつなぎます。全体の頂点数が V × 2 のグラフをつくるのです。
頂点番号 i の頂点の IN と OUT の index は 2 * i と 2 * i + 1 にします。するとスタート地点からゴールにたどり着けるかどうかは 1 番目（2 * 0 + 1）の頂点から 2 * (V – 1) 番目（2 * (V – 1) + 1）の頂点にたどり着けるかということを調べればよいことになります。
前問で定義した BFSメソッドを繰り返し呼び出して最大フローを計算します。これで「最小で何円払う必要があるか？」はわかります。つぎに壁の立て方ですが、これは残りの容量をつかって開始点から IN にはたどり着くことができるけれども OUT にはたどり着けない頂点を調べればわかります。
|
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
using System; using System.Collections.Generic; using System.Linq; class Program { // long BFS(long[,] mat, int V, int start, int goal)の定義は同じなので省略 static void Main() { int V, E; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); V = vs[0]; E = vs[1]; } long[,] mat = new long[2 * V, 2 * V]; for (int i = 0; i < E; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; mat[2 * a + 1, 2 * b] = long.MaxValue; mat[2 * b + 1, 2 * a] = long.MaxValue; } int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int i = 0; i < V; i++) mat[2 * i, 2 * i + 1] = C[i]; long total = 0; while (true) { long add = BFS(mat, 2 * V, 1, 2 * (V - 1)); total += add; if (add == 0) break; } // IN にはたどり着くことができるけれども OUT にはたどり着けない頂点を調べる bool[] visits = BFS2(mat, 2 * V, 1); List<int> cuts = new List<int>(); for (int i = 0; i < V; i++) { if(visits[2 * i] && !visits[2 * i + 1]) cuts.Add(i + 1); // 頂点番号は 1 から始まるので } Console.WriteLine(total); Console.WriteLine(cuts.Count); Console.WriteLine(string.Join(" ", cuts)); } // 残余ネットワークをつかって start から到達可能な頂点を調べる static bool[] BFS2(long[,] mat, int V, int start) { bool[] visits = new bool[V]; Queue<int> q = new Queue<int>(); q.Enqueue(start); visits[start] = true; while (q.Count > 0) { int cur = q.Dequeue(); for (int i = 0; i < mat.GetLength(0); i++) { if (mat[cur, i] > 0) { if (visits[i]) continue; visits[i] = true; q.Enqueue(i); } } } return visits; } } |
