AtCoder NoviStepsを埋めてみる(30) 二重辺連結成分分解の続きです。今回は最大流問題です。
最大流問題は、容量制限付きネットワークで源点から終点へ流せる量の最大値を求める問題です。配送・通信・割当てなど多くの最適化に使われます。
最小カット問題は、ネットワークを2つのグループに分けるとき、切る辺の容量（重み）の合計が最小になる切り方を求める問題です。最大流問題と密接に対応し、最大流の値と最小カット容量は等しくなります。
ac-library-csharp というライブラリには MfGraph<T> クラスがあり、これを使えば簡単に最大流問題を解くことができます。今回はこれを使い倒すことにします。
E – 最大流
問題の概要
V 個の街と E 本の水道管があり、i 本目の水道管は街 u[i] から街 v[i] へ水を最大で c[i] だけ流すことができる。街 1 から街 V へ流せる水の量の最大値を求めよ。
なんのひねりもない、そのまんまの最大流問題です。ライブラリを使えば一瞬です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
using AtCoder; class Program { static void Main() { int[] ve = Console.ReadLine().Split().Select(int.Parse).ToArray(); int V = ve[0]; int E = ve[1]; AtCoder.MfGraph<long> G = new MfGraph<long>(V); for (int i = 0; i < E; i++) { int[] uvc = Console.ReadLine().Split().Select(int.Parse).ToArray(); int u = uvc[0] - 1; int v = uvc[1] - 1; int c = uvc[2]; G.AddEdge(u, v, c); } Console.WriteLine(G.Flow(0, V - 1)); } } |
A69 – Bipartite Matching
問題の概要
あるクラスには N 人の生徒がおり、席も N 個ある。
席替えで「生徒 i は席 j を希望している」といった情報が与えられる。
最大何人の希望をかなえられるかを求めよ。
これは二部グラフの最大マッチング問題です。
まず N × 2 + 2 個の頂点を用意します。頂点 0 から頂点 N – 1 は生徒を表し、頂点 N から 頂点 2 × N – 1 は席を表しています。そして頂点 2 × N は始点となる超頂点 S、頂点 2 × N + 1 は終点となる超頂点 T を表しています。
生徒 i が席 j を希望しているのであれば、頂点 i から頂点 j + N へ辺を張ります。さらに頂点 S からすべての生徒へ向けて辺を張り、すべての席から頂点 T へ辺を張ります。 辺の容量はすべて 1 とします。
最後に頂点 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 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); AtCoder.MfGraph<int> G = new MfGraph<int>(2 * N + 2); int s = 2 * N; int t = 2 * N + 1; for (int u = 0; u < N; u++) { char[] vs = Console.ReadLine().ToArray(); for (int v = 0; v < N; v++) { if (vs[v] == '#') G.AddEdge(u, v + N, 1); } G.AddEdge(s, u, 1); G.AddEdge(u + N, t, 1); } Console.WriteLine(G.Flow(s, t)); } } |
E – プレゼント配布
問題の概要
パーティーに参加してくれた人にプレゼントを渡したい。
参加者の人数は N であり、プレゼントの種類数は M である。
i 番目の種類のプレゼントは B[i] 個ある。i 番目の参加者は K[i] 種類のプレゼントを希望しており、プレゼント C[i, 0], C[i, 1], …, C[i, K[i] – 1] を希望している。
最大何人に希望するプレゼントを渡すことができるだろうか？
これも二部グラフの最大マッチング問題です。
まず N × M + 2 個の頂点を用意します。頂点 0 から頂点 N – 1 は参加者を表し、頂点 N から 頂点 N + M – 1 はプレゼントを表しています。そして頂点 N + M は始点となる超頂点 S、頂点 N + M + 1 は終点となる超頂点 T を表しています。そして参加者 i が プレゼント c を希望しているのであれば、頂点 i から頂点 c + N へ辺を張ります。これらの辺の容量はすべて 1 とします。
ここまでは A69 – Bipartite Matching と同じです。頂点 S からすべての参加者へ向けて容量 1 の辺を張るのですが、すべてのプレゼントから頂点 T へ張る辺の容量は 1 ではなく B[i] とします。同じプレゼントと B[i] 個までならつながってもよいからです。
あとは前問と同様に頂点 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 |
using AtCoder; class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); AtCoder.MfGraph<int> G = new MfGraph<int>(N + M + 2); int s = N + M; int t = N + M + 1; for (int i = 0; i < N; i++) { int[] kc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int j = 1; j < kc.Length; j++) { int c = kc[j] - 1; G.AddEdge(i, c + N, 1); } } // 超頂点 S から参加者へ for (int i = 0; i < N; i++) G.AddEdge(s, i, 1); // プレゼントから超頂点 T へ for (int i = 0; i < M; i++) G.AddEdge(N + i, t, B[i]); Console.WriteLine(G.Flow(s, t)); } } |
D – Maxflow
問題の概要
N 行 M 列のマス目がある。それぞれのマスは障害物が置かれているか空であるかのどちらかの状態である。
これらのマスに 1 × 2 の大きさのタイルを置きたい。タイルは縦または横に連続する 2 つの空マスの上に置くことができるが、タイルを盤面からはみ出すように置くことや、障害物や他のタイルがすでに置かれているマスにタイルを重ねることはできない。
最大でいくつのタイルを置くことができるか求めよ。また実際にその最大値を達成する方法を 1 つ示せ。
これも二部グラフの最大マッチング問題です。
まずマス目を市松模様に塗ります。n 行 m 列 が偶数であれば黒、そうでなければ白とします。隣り合う白黒のマスが両方とも空きマスであれば黒マスから白マスへ容量 1 の辺を張ります。また超頂点 S からすべての空き黒マスへ、すべての空き白マスから超頂点へ 容量 1 の辺を張ります。そして S から T へフローを流せば置くことができるタイルの最大数がわかります。
どこへタイルを置くことができるかですが、Edgesメソッドですべての辺を取得し、このなかからマス同士のあいだに張られている流量が 1 である辺を探します。FromプロパティとToプロパティをみればどのマスが選ばれているかがわかります。あとはそのマスを ‘<‘, ‘>’, ‘^’, ‘v’ に置き換えて出力するだけです。
|
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 |
using AtCoder; class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; char[,] grid = new char[N, M]; for (int r = 0; r < N; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < M; c++) grid[r, c] = vs[c]; } AtCoder.MfGraph<int> G = new MfGraph<int>(N * M + 2); int s = N * M; int t = N * M + 1; for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { if ((r + c) % 2 == 0 && grid[r, c] == '.') { if (r - 1 >= 0 && grid[r - 1, c] == '.') G.AddEdge(r * M + c, (r - 1) * M + c, 1); if (r + 1 < N && grid[r + 1, c] == '.') G.AddEdge(r * M + c, (r + 1) * M + c, 1); if (c - 1 >= 0 && grid[r, c - 1] == '.') G.AddEdge(r * M + c, r * M + c - 1, 1); if (c + 1 < M && grid[r, c + 1] == '.') G.AddEdge(r * M + c, r * M + c + 1, 1); G.AddEdge(s, r * M + c, 1); } if ((r + c) % 2 == 1 && grid[r, c] == '.') G.AddEdge(r * M + c, t, 1); } } Console.WriteLine(G.Flow(s, t)); var edges = G.Edges(); foreach (var edge in edges) { if (edge.Flow == 1 && edge.From != s && edge.To != t) { int v_min = Math.Min(edge.From, edge.To); int v_max = Math.Max(edge.From, edge.To); int r_min = v_min / M; int c_min = v_min % M; int r_max = v_max / M; int c_max = v_max % M; if (r_min == r_max) { grid[r_min, c_min] = '>'; grid[r_max, c_max] = '<'; } else { grid[r_min, c_min] = 'v'; grid[r_max, c_max] = '^'; } } } for (int r = 0; r < N; r++) { char[] vs = new char[M]; for (int c = 0; c < M; c++) vs[c] = grid[r, c]; Console.WriteLine(new string(vs)); } } } |
077 – Planes on a 2D Plane（★7）
077 – Planes on a 2D Plane（★7）
問題の概要
N 機の飛行機が航行している。
i = 1, 2, …, N に対し、i 番目の飛行機の位置座標は時刻 0 において座標 (AX[i], AY[i]) だった。
飛行機はいずれも向き 1, …, 8 のいずれかを向いて航行している。
座標 (x, y) に存在する向き d の飛行機は、時間 1 が経過すると
d = 1：(x + 1, y)
d = 2：(x + 1, y + 1)
d = 3：(x, y + 1)
d = 4：(x – 1, y + 1)
d = 5：(x – 1, y)
d = 6：(x – 1, y – 1)
d = 7：(x, y – 1)
d = 8：(x + 1, y – 1)
へ移動する。飛行機が途中で向きを変えることはない。
時刻 T において、座標 (BX[1], BY[1]), (BX[2], BY[2]), …, (BX[N], BY[N]) に飛行機が存在するという報告を受けた。
報告に矛盾しないような N 機の飛行機の向きの組み合わせが存在するかを判定し、存在する場合は一例を示せ。
これも二部グラフの最大マッチング問題です。
まず N × 2 + 2 個の頂点を用意します。頂点 0 から 頂点 N – 1 が移動前の飛行機の座標、頂点 N から 頂点 N × 2 – 1 が移動後の飛行機の座標を表します。頂点 N × 2 が超頂点 S、頂点 N × 2 + 1 が超頂点 T です。
それぞれの飛行機 i を 8 方向に移動させてみて (BX[i], BY[i]) と一致するのであれば頂点 i から頂点 i + N へむけて容量 1 の辺を張ります。また S から 頂点 0 から 頂点 N – 1 のそれぞれの頂点へ、頂点 N から 頂点 N × 2 – 1 のそれぞれの頂点から頂点 T へ容量 1 の辺を張ります。このようなグラフを構築したらフローを流します。
報告に矛盾しないような N 機の飛行機の向きの組み合わせが存在するのであれば最大マッチングの数は N と一致するはずです。その場合は頂点 0 から頂点 N × 2 – 1 のあいだに張られている流量 1 の辺がどれか調べることで移動前の座標と移動後の座標がどのように対応しているかがわかります。ここから飛行機 i の向きもわかります。
|
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 |
using AtCoder; class Program { static void Main() { int[] nt = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nt[0]; int T = nt[1]; int[] X1 = new int[N]; int[] Y1 = new int[N]; for (int i = 0; i < N; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); X1[i] = xy[0]; Y1[i] = xy[1]; } AtCoder.MfGraph<int> G = new MfGraph<int>(N * 2 + 2); int s = N * 2; int t = N * 2 + 1; int[] X2 = new int[N]; int[] Y2 = new int[N]; Dictionary<string, int> after = new Dictionary<string, int>(); for (int i = 0; i < N; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); X2[i] = xy[0]; Y2[i] = xy[1]; after.Add($"{xy[0]},{xy[1]}", i + N); G.AddEdge(i + N, t, 1); } (int, int)[] diffs = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]; for (int i = 0; i < N; i++) { foreach (var diff in diffs) { string str = $"{X1[i] + diff.Item1 * T},{Y1[i] + diff.Item2 * T}"; if (after.ContainsKey(str)) G.AddEdge(i, after[str], 1); } G.AddEdge(s, i, 1); } int flow = G.Flow(s, t); if (flow != N) { Console.WriteLine("No"); return; } Console.WriteLine("Yes"); int[] ans = new int[N]; var edges = G.Edges(); foreach (var edge in edges) { if (edge.Flow == 1 && edge.From != s && edge.To != t) { int from = edge.From; int to = edge.To - N; for (int i = 0; i < 8; i++) { if (X1[from] + diffs[i].Item1 * T == X2[to] && Y1[from] + diffs[i].Item2 * T == Y2[to]) { ans[from] = i + 1; break; } } } } Console.WriteLine(string.Join(" ", ans)); } } |
G – Push Simultaneously
問題の概要
平面上に N 人の人と N 個のボタンがあり、人 i の座標は (sx[i], sy[i]) であり、ボタンの座標は (gx[i], gy[i]) である。
人は秒速 1 メートル以下の速さで好きな方向に進むことができる。
N 人の人をそれぞれ移動させた後、N 個のボタンを一斉に押したい。目標を達成するために必要な時間の最小値を求めよ。
time 後に目標達成できるかどうかを判定するメソッドを定義して、決め打ち二分探索法で目標達成できる時間の最小値を調べます。time 後に目標達成できるかどうかを判定するメソッドは、人がいる頂点から時間 time 以内にたどり着ける頂点にむけて辺を張り、s → 人 i、ボタン i → t にも辺を張り、フローを流したときに最大流が N と一致するかどうかを調べればよいです。
double 型の二分探索ですが、コメントにあるとおり、大きな値の場合いつまでたっても終了条件を満たさない場合があります。なので decimal 型を使っています。decimal 型は 10^28 が限界なので 座標が 10^18 のような大きな値だと距離を求めるときにそのまま二乗すると誤差が生じます。なので距離の計算までは double 型をつかってキャストした値をつかって最大マッチングを求める処理と二分探索をしています。
|
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 |
using AtCoder; class Program { static decimal BinarySearch(decimal ok, decimal ng, Predicate<decimal> Ok) { while (Math.Abs(ok - ng) > (decimal)0.0000001) { decimal mid = (ok + ng) / 2; if (Ok(mid)) ok = mid; else ng = mid; } return ok; } static void Main() { int N = int.Parse(Console.ReadLine()); double[] SX = new double[N]; double[] SY = new double[N]; for (int i = 0; i < N; i++) { long[] xy = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); SX[i] = xy[0]; SY[i] = xy[1]; } double[] GX = new double[N]; double[] GY = new double[N]; for (int i = 0; i < N; i++) { long[] xy = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); GX[i] = xy[0]; GY[i] = xy[1]; } decimal[,] dists = new decimal[N, N]; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { double d2 = double.Pow(GX[b] - SX[a], 2) + double.Pow(GY[b] - SY[a], 2); dists[a, b] = (decimal)Math.Sqrt(d2); } } bool F(decimal time) { AtCoder.MfGraph<int> G = new MfGraph<int>(N * 2 + 2); int s = N * 2; int t = N * 2 + 1; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { if (dists[a, b] <= time) { G.AddEdge(a, b + N, 1); } } } for (int i = 0; i < N; i++) { G.AddEdge(s, i, 1); G.AddEdge(i + N, t, 1); } return G.Flow(s, t) == N; } decimal ok = long.MaxValue; decimal ng = 0; decimal ans = BinarySearch(ok, ng, mid => F(mid)); Console.WriteLine(ans); } } |
D – 浮気予防
問題の概要
高橋君は、女の子と仲良くなるために、自前のSNSを使っている。SNSで友人関係にある人を辿って行き、見つけた女の子にメッセージを送る。なぎさちゃんは、高橋君のメッセージを女の子が見ることがないように、このSNSに対して、工作を行なおうとしている。
行える工作活動は以下の 2 つである。
特定の二人の友人関係を解消する
特定の一人のパスワードを変え、ログイン不能にする（高橋君のパスワードは変更できない）。友人関係が解消されると、高橋君は、その二人の間を辿ることができなくなり、パスワードを変更すると、その人は、メッセージを見ることが不可能になる。
なぎさちゃんは、出来るだけ工作の回数を少なくして、予めマークした女の子達が、高橋君のメッセージを閲覧できないようにしたい。なぎさちゃんが工作を行なう必要のある回数を求めよ。
SNS の登録人数に 1 を加えた個数の頂点を用意します。頂点 0 は高橋君、頂点 1 から頂点 N – 1 まではそれ以外の SNS のユーザーを表しています。頂点 N は超頂点です。
友人関係があるなら頂点同士に双方向に容量 1 の辺を張ります。またマークしている女の子から超頂点に容量 1 の辺を張ります。
「特定の二人の友人関係を解消する」とは友人間に張られた辺を切ることを意味しています。また「特定の一人のパスワードを変え、ログイン不能にする」は超頂点への辺を切ることを意味しています。辺を切ることで 頂点 0 から頂点 N までたどり着けないようにしてしまえばよいのです。
工作の回数を最小にして目的を達成するためには頂点 0 と頂点 N との間の最小カットを求めればよいです。最小カットは最大流と同じ値になります。
テストケースでは G が 0 の場合があります。この場合、P に相当する行が存在しないのではなく空文字列の入力があるので注意が必要です。
|
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 |
using AtCoder; class Program { static void Main() { int[] nge = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int G, int E) = (nge[0], nge[1], nge[2]); int[] P = []; if(G > 0) P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); else _ = Console.ReadLine(); // G == 0 のとき、入力は空文字列となる AtCoder.MfGraph<int> g = new MfGraph<int>(N + 1); for (int i = 0; i < E; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int u, int v) = (uv[0], uv[1]); g.AddEdge(u, v, 1); g.AddEdge(v, u, 1); } foreach (var p in P) g.AddEdge(p, N, 1); var ans = g.Flow(0, N); Console.WriteLine(ans); } } |
G – Typical Path Problem
問題の概要
N 頂点 M 辺の連結な単純無向グラフ G が与えられる。
頂点 B を経由して頂点 A と頂点 C を結ぶ単純パスが存在するか判定せよ。
単純パスは同じ頂点や辺を複数回通ってはなりません。
頂点 B を経由して頂点 A と頂点 C を結ぶ単純パスが存在するのであれば、頂点 B から頂点 A へのパスが存在し、それとは異なる頂点をとおる頂点 B から頂点 C へのパスが存在するはずです。
つながっている頂点間に相互に容量 1 の辺を張り、頂点 A と頂点 C から超頂点 T へ容量 1 の辺を張る。そして頂点 B から頂点 T へフローを流したときの最大流が 2 であるかどうかで判定できそうですが、これだけでは不十分です。これだと同じ辺を通らない頂点 B を経由して頂点 A と頂点 C を結ぶパスが存在するかの判定はできますが、同じ頂点を複数回通ってしまうパスも “Yes” と判定してしまうことになります。
そこでひとつの同じ頂点のなかに「入頂点」と「出頂点」のふたつをつくります。頂点 i の入頂点は i × 2、出頂点は i × 2 + 1 とします。
グラフ G において 頂点 u と頂点 v のあいだに無向辺があるのであれば、u × 2 + 1 から v × 2 へ、v × 2 + 1 から u × 2 へそれぞれ容量 1 の辺を張ります。また入頂点から出頂点へも容量 1 の辺をはります。最後に A × 2 + 1 と C × 2 + 1 から超頂点へ容量 1 の辺を張り、B × 2 + 1 から超頂点に向けてフローを流します。流量が 2 であれば条件を満たす単純パスが存在します。
|
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 |
using AtCoder; class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M) = (nm[0], nm[1]); int[] abc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int A, int B, int C) = (abc[0] - 1, abc[1] - 1, abc[2] - 1); AtCoder.MfGraph<int> G = new MfGraph<int>(N * 2 + 1); int t = N * 2; // 同一頂点内の入頂点 → 出頂点 for (int i = 0; i < N; i++) G.AddEdge(i * 2, i * 2 + 1, 1); // 与えられたグラフで u と v のあいだに辺があるなら // u の出頂点 → v の入頂点、v の出頂点 → u の入頂点へ for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int u, int v) = (uv[0] - 1, uv[1] - 1); G.AddEdge(u * 2 + 1, v * 2, 1); G.AddEdge(v * 2 + 1, u * 2, 1); } // A, C の出頂点 → 超頂点へ G.AddEdge(A * 2 + 1, t, 1); G.AddEdge(C * 2 + 1, t, 1); Console.WriteLine(G.Flow(B * 2 + 1, t) == 2 ? "Yes" : "No"); } } |
G – Builder Takahashi
問題の概要
N 頂点 M 辺の単純連結無向グラフが与えられる。
頂点 1 と頂点 N 以外の頂点を通行止めにすることで頂点 1 から頂点 N へ行くことができないようにしたい。ただし頂点 i を通行止めにするには C[i] のコストが必要である。
必要なコストの最小値を求めよ。
この問題もひとつの同じ頂点のなかに「入頂点」と「出頂点」のふたつをつくることで対応します。
頂点 u と頂点 v のあいだに無向辺があるのであれば、u × 2 + 1 から v × 2 へ、v × 2 + 1 から u × 2 へそれぞれ容量 ∞ の辺を張ります。∞ はこの辺は切られてはならないという意味です。∞ として使う値はC の総和より充分大きく M 倍したときにオーバーフローしない値ならなんでもよいです。
次に頂点 i の入頂点から出頂点へ容量 C[i] の辺を張ります。
そのあと 1 から (N – 1) * 2 に向けて（頂点 0 の出頂点から頂点 N – 1 の入頂点に向けて）フローを流して最小カットを求めます。
通行止めにする頂点を求めるには MinCut(s) メソッドを呼び出します。このメソッドは残余グラフにおいて頂点 i が頂点 s からたどり着くことができるなら true、そうではないなら false である配列を返します。mincut[i * 2] == true かつ mincut[i * 2 + 1] == false である i が残余グラフにおいてカットエッジとなる部分です。
|
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 |
using AtCoder; class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M) = (nm[0], nm[1]); int[] U = new int[M]; int[] V = new int[M]; for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int u, int v) = (uv[0] - 1, uv[1] - 1); U[i] = u; V[i] = v; } int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); AtCoder.MfGraph<long> G = new MfGraph<long>(N * 2); for (int i = 0; i < N; i++) G.AddEdge(i * 2, i * 2 + 1, C[i]); // 「無限大」を表す数。C の総和より大きく M 倍したときにオーバーフローしない値ならよい long inf = (long)Math.Pow(10, 12); for (int i = 0; i < M; i++) { G.AddEdge(U[i] * 2 + 1, V[i] * 2, inf); G.AddEdge(V[i] * 2 + 1, U[i] * 2, inf); } long flow = G.Flow(1, (N - 1) * 2); Console.WriteLine(flow); List<int> P = new List<int>(); bool[] mincut = G.MinCut(1); for (int i = 0; i < N; i++) { if (mincut[i * 2] && !mincut[i * 2 + 1]) P.Add(i + 1); } Console.WriteLine(P.Count); Console.WriteLine(string.Join(" ", P)); } } |
F – Lotus Leaves
問題の概要
長方形の池があります。 池は縦 H 行、横 W 列のマス目状に分割されている。
池のいくつかのマスには蓮 (はす) の葉が浮かんでいる。葉 S にはカエルが乗っており、今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプすることを繰り返して別の葉である T まで移動しようとしている。
S, T 以外の葉を何枚か取り除くことでカエルが葉 S から葉 T まで移動できないようにしたい。この目標が達成可能か判定し、達成可能であれば取り除く葉の枚数の最小値を求めよ。
マスを頂点とみなし、入頂点と出頂点を設定して最小カットを求める方法でもできるのですが、もっと少ない頂点数で正解する方法があります。
カエルが効率よく S から T まで移動するときは、縦移動と横移動を交互に繰り返します。
そこで H + W + 2 個の頂点を用意します。頂点 0 から 頂点 H – 1 はカエルが上から r 行目にいることを、頂点 H から 頂点 H + W – 1 はカエルが左から c 列目にいることを意味しています。蓮の葉が (r, c) にあるとカエルの現在位置が (r, ◯) にいる状態から (△, c) にいる状態に移行できることになるので頂点 r と 頂点 H + c のあいだに相互に辺を張ります。蓮の葉を取り除くということはこの辺を取り除くことを意味します。
初期状態でカエルが (r, c) にいるということは現在位置が (r, ◯) と解釈することもできるし、(△, c) と解釈することもできます。なので超頂点 S から頂点 r と頂点 H – c にむけて容量 ∞ の辺を張ります。
ゴールが (r, c) であることもその位置が (r, ◯) と解釈することもできるし、(△, c) と解釈することもできるので、頂点 r と頂点 H – c から超頂点 T にむけて容量 ∞ の辺を張ります。
頂点 S から T にむけてフローを流して最小カットを求めます。最小カットが ∞ の場合は蓮の葉をどのように取り除いてもカエルはゴールにたどり着くことができるので -1 が答えです。そうでない場合は最小カットが答えです。
|
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 |
using AtCoder; class Program { static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int H, int W) = (hw[0], hw[1]); AtCoder.MfGraph<long> G = new MfGraph<long>(H + W + 2); int s = H + W; int t = H + W + 1; long inf = int.MaxValue; for (int r = 0; r < H; r++) { string str = Console.ReadLine(); for (int c = 0; c < W; c++) { if (str[c] == 'o') { G.AddEdge(r, c + H, 1); G.AddEdge(c + H, r, 1); } if (str[c] == 'S') { G.AddEdge(s, r, inf); G.AddEdge(s, c + H, inf); } if (str[c] == 'T') { G.AddEdge(r, t, inf); G.AddEdge(c + H, t, inf); } } } long flow = G.Flow(s, t); // これはダメ！ Console.WriteLine(flow == inf ? flow : -1); // inf の辺を二箇所切らないといけないケースだと落とされる Console.WriteLine(flow < inf ? flow : -1); } } |
E – 送電ネットワークの停電危機
問題の概要
N 個の工場と K 個の発電所、それらをつなぐ M 本の送電線がある。
工場 i は B[i] メガワット以上の電力を必要とし、発電所 k は 0 以上 W[k] メガワット以下の任意の量の電力を供給できる。
Q 個のイベントが順番に発生する。t 番目のイベントでは、発電所 S[t] が使用不能になる。一度使用不能になった発電所は以降ずっと使用不能のままである。
各イベントが発生した直後の状態において、すべての工場が必要な電力を確保して稼働を継続できるかどうかを判定せよ。
N + K + 2 個の頂点を用意します。工場 i を頂点 i、発電所 k を頂点 N + k とします。送電線でつながっている地点に相当する頂点同士のあいだに無向辺を張ります。そして超頂点 S から稼働している発電所へ容量 W[k]の有向辺を、すべての工場から超頂点 T へ容量 B[i] の有向辺を張ります。そして超頂点 S から T へフローを流して最大流を求めます。この値が B の総和と一致しているのであれば、すべての工場が必要な電力を確保できることになります。
イベントがおきるたびに超頂点 S から使用不能になった発電所には辺を張らないグラフを構築して最大流を調べます。工場、発電所、イベントの回数の最大数がそれぞれ 32 なので毎回グラフを再構築したとしても充分間に合います、
|
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 |
using AtCoder; class Program { static void Main() { int[] nkm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int K, int M) = (nkm[0], nkm[1], nkm[2]); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] W = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long sumB = 0; foreach (long b in B) sumB += b; int s = N + K; int t = N + K + 1; long inf = int.MaxValue; int[] U = new int[M]; int[] V = new int[M]; int[] C = new int[M]; for (int i = 0; i < M; i++) { int[] uvc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int u, int v, int c) = (uvc[0] - 1, uvc[1] - 1, uvc[2]); U[i] = u; V[i] = v; C[i] = c; } // 発電所 set が故障している状態で送れる電力の総和を求める long F(HashSet<int> set) { AtCoder.MfGraph<long> G = new MfGraph<long>(N + K + 2); for (int i = 0; i < M; i++) { G.AddEdge(U[i], V[i], C[i]); G.AddEdge(V[i], U[i], C[i]); } for (int i = 0; i < N; i++) G.AddEdge(i, t, B[i]); for (int i = 0; i < K; i++) { if (!set.Contains(i)) G.AddEdge(s, i + N, W[i]); } return G.Flow(s, t); } int Q = int.Parse(Console.ReadLine()); HashSet<int> set = new HashSet<int>(); for (int i = 0; i < Q; i++) { int v = int.Parse(Console.ReadLine()); v--; set.Add(v); Console.WriteLine(F(set) >= sumB ? "Yes" : "No"); } } } |
E – Wi-Fiアクセスポイントの設置
問題の概要
N 頂点 M 辺の二部グラフが与えられる。最小頂点被覆の大きさを求めよ。
ただしこの二部グラフは連結グラフであるとは限らない。
頂点からなる集合のうち、それらの頂点から出ている辺をすべて集めるとすべての辺を覆うようなものを点被覆とよびます。最小頂点被覆問題とは、最小サイズの点被覆を求める問題です。
二部グラフの最小頂点被覆の大きさは、最大マッチングの大きさと一致します。
「教育棟」に相当する頂点から「研究棟」に相当する頂点に辺を張り、超頂点 S からすべての「教育棟」へ、すべての研究棟から超頂点 T へ辺を張り、S から T へフローを流して最大流を求めれば、これが最大マッチングの大きさと一致し、解とも一致する値が得られるのですが、どの頂点が「教育棟」と「研究棟」に相当するのかがわからないので隣り合う頂点が同じ色にならないように黒と白で彩色します。
彩色したら容量 1 の辺を張ります。超頂点 S からすべての黒頂点へ、黒頂点から元のグラフで辺が張られている頂点へ、すべての白頂点から超頂点 T へ辺を張ります。このとき黒頂点から白頂点へ相互に辺を張ってはいけません。
最後に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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
using AtCoder; class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M) = (nm[0], nm[1]); List<int>[] G1 = new List<int>[N]; for (int i = 0; i < N; i++) G1[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int u, int v) = (uv[0] - 1, uv[1] - 1); G1[u].Add(v); G1[v].Add(u); } bool[] seen = new bool[N]; int[] colors = new int[N]; void Dfs(int cur) { if (seen[cur]) return; seen[cur] = true; foreach (int next in G1[cur]) { colors[next] = colors[cur] == 1 ? -1 : 1; Dfs(next); } } for (int i = 0; i < N; i++) { if (!seen[i]) { colors[i] = 1; Dfs(i); } } bool[] isblacks = new bool[N]; for (int i = 0; i < N; i++) isblacks[i] = colors[i] == 1; AtCoder.MfGraph<int> G2 = new MfGraph<int>(N + 2); int s = N; int t = N + 1; for (int i = 0; i < N; i++) { if (isblacks[i]) { G2.AddEdge(s, i, 1); foreach (var next in G1[i]) G2.AddEdge(i, next, 1); } else G2.AddEdge(i, t, 1); } Console.WriteLine(G2.Flow(s, t)); } } |
C – 広告
問題の概要
R × C 個のマスからなるグリッドがある。マスには ‘.’ か ‘*’ が書かれている。
‘.’ が隣り合わないように選ぶとき、最大で何個選ぶことができるだろうか？
この問題は最大独立集合の大きさを求める問題です。
最大独立集合問題は、グラフ理論において、与えられたグラフ G に対して、頂点集合 V’ うち V’ 内の頂点間に枝が存在しないようなもの（独立集合）で大きさが最大のものを求める問題です。最大安定集合問題とも言います。この問題は、NP困難であることが知られていますが、二部グラフであれば多項式時間で解くことができます。
二部グラフであれば最大独立集合は（頂点数 – 最大マッチングの大きさ）となります。
マスを市松模様に塗り、隣り合うマスが両方とも ‘.’ であれば黒マスから白マスに容量 1 の辺を張ります。超頂点 S から ‘.’ であるすべての黒マスへ、’.’ であるすべての白マスから超頂点 T へ容量 1 の辺を張ります。そして 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
using AtCoder; class Program { static void Main() { int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int R, int C) = (rc[0], rc[1]); char[,] grid = new char[R, C]; for (int r = 0; r < R; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < C; c++) grid[r, c] = vs[c]; } AtCoder.MfGraph<int> G = new MfGraph<int>(R * C + 2); int s = R * C; int t = R * C + 1; int cnt = 0; // '.' の数 for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { if (grid[r, c] == '.') { int idx = r * C + c; if ((r + c) % 2 == 0) G.AddEdge(s, idx, 1); else G.AddEdge(idx, t, 1); cnt++; } } } for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { int idx = r * C + c; if ((r + c) % 2 == 0 && grid[r, c] == '.') { if (r - 1 >= 0 && grid[r - 1, c] == '.') G.AddEdge(idx, (r - 1) * C + c, 1); if (r + 1 < R && grid[r + 1, c] == '.') G.AddEdge(idx, (r + 1) * C + c, 1); if (c - 1 >= 0 && grid[r, c - 1] == '.') G.AddEdge(idx, r * C + c - 1, 1); if (c + 1 < C && grid[r, c + 1] == '.') G.AddEdge(idx, r * C + c + 1, 1); } } } Console.WriteLine(cnt - G.Flow(s, t)); } } |
N – 壁の建設計画
問題の概要
縦横 H × W マスのグリッドがある。
各マスの状態は「壁がないマス」か「壁があるマス」のいずれかであり、はじめはすべてのマスは壁がないマスである。
現在いるマスから上、下、左、右でつながっている壁がないマスであれば移動することができる。
マス (0, 0) から (H – 1, W – 1) へたどりつけないようにいくつかのマスを壁があるマスに変更したい。マス (i, j) に壁を建てるにはコスト C[i, j] が必要である。(1, 1), (H, W) には壁を建てられない。
必要なコストの最小値を求めよ。またその時の壁の立て方を出力せよ。
各マスのなかに入頂点と出頂点をつくります。そして移動可能なマスの出頂点から入頂点へ容量 ∞ の辺を張り、入頂点から出頂点へ容量 1 の辺を張ります。そしてマス (0, 0) の出頂点から (H – 1, W – 1) の入頂点へフローを流して最小カットを求めます。これが求めるべき最小コストです。
壁を立てるマスを求める方法ですが、カットの境界になる部分がわかればよいです。MfGraph.MinCut を呼び出し、mincut[マス(r, c)の入頂点] が true で mincut[マス(r, c)の出頂点] が false になっているマスを探せばよいです。
|
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 |
using AtCoder; class Program { static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int H, int W) = (hw[0], hw[1]); MfGraph<long> G = new MfGraph<long>(H * W * 2); int GetInIdx(int r, int c) => (r * W + c) * 2; int GetOutIdx(int r, int c) => (r * W + c) * 2 + 1; for (int r = 0; r < H; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < W; c++) G.AddEdge(GetInIdx(r, c), GetOutIdx(r, c), vs[c]); } long inf = (long)Math.Pow(10, 12); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if(r + 1 < H) G.AddEdge(GetOutIdx(r, c), GetInIdx(r + 1, c), inf); if (r - 1 >= 0) G.AddEdge(GetOutIdx(r, c), GetInIdx(r - 1, c), inf); if (c + 1 < W) G.AddEdge(GetOutIdx(r, c), GetInIdx(r, c + 1), inf); if (c - 1 >= 0) G.AddEdge(GetOutIdx(r, c), GetInIdx(r, c - 1), inf); } } long ans = G.Flow(GetOutIdx(0, 0), GetInIdx(H - 1, W - 1)); Console.WriteLine(ans); bool[] mincut = G.MinCut(GetOutIdx(0, 0)); for (int r = 0; r < H; r++) { char[] vs = new char[W]; for (int c = 0; c < W; c++) { if (mincut[GetInIdx(r, c)] == true && mincut[GetOutIdx(r, c)] == false) vs[c] = '#'; else vs[c] = '.'; } Console.WriteLine(new string(vs)); } } } |
E – 柵
問題の概要
縦 H マス横 W マスのグリッドのいくつかのマスにヤギがいる。
ヤギは上下左右の隣接する柵のないマスに移動することができる。そしてグリッドの端の行や列にたどりついたとき、グリッドの外に出ることができる。
ヤギのいないいくつかのマスに柵を設置して、どのヤギも、移動をくりかえしてグリッドの外に出ることができないようにしたい。
設置すべき柵の最小個数を求めよ。
各マスのなかに入頂点と出頂点をつくり、移動可能なマスの出頂点から入頂点へ容量 ∞ の辺を張り、入頂点から出頂点へ容量 1 の辺を張ります。超頂点 S からヤギがいるマスの出頂点へ容量 ∞ の辺を張り、グリットの出頂点から超頂点 T へ容量 ∞ の辺を張ります。
そして超頂点 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 46 47 48 49 50 |
using AtCoder; class Program { static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int H, int W) = (hw[0], hw[1]); AtCoder.MfGraph<long> G = new MfGraph<long>(H * W * 2 + 2); int s = H * W * 2; int t = H * W * 2 + 1; long inf = (long)Math.Pow(10, 12); int GetInIdx(int r, int c) => (r * W + c) * 2; int GetOutIdx(int r, int c) => (r * W + c) * 2 + 1; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) { G.AddEdge(GetInIdx(r, c), GetOutIdx(r, c), 1); if(vs[c] == 'X') G.AddEdge(s, GetOutIdx(r, c), inf); if (r == 0 || r == H - 1 || c == 0 || c == W - 1) G.AddEdge(GetOutIdx(r, c), t, inf); } } for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if(r + 1 < H) G.AddEdge(GetOutIdx(r, c), GetInIdx(r + 1, c), inf); if (r - 1 >= 0) G.AddEdge(GetOutIdx(r, c), GetInIdx(r - 1, c), inf); if (c + 1 < W) G.AddEdge(GetOutIdx(r, c), GetInIdx(r, c + 1), inf); if (c - 1 >= 0) G.AddEdge(GetOutIdx(r, c), GetInIdx(r, c - 1), inf); } } long flow = G.Flow(s, t); Console.WriteLine(flow < inf ? flow : -1); } } |
C – 天下一美術館
問題の概要
黒マスと白マスからなる縦 H、横 W のグリッドがふたつある。
① 黒マスから白マスへの変換、② 白マスから黒マスへの変換、③ 上下左右の 4 方向に隣り合ったマス目の交換の 3 種類あり、どれもコストが 1 かかる。
一方のグリッドに変換操作することで他方のグリッドと一致させたい。この操作に必要な最小コストを求めよ。
隣り合うマスが異なる色で両方とも色を変えなければならない場合、③ で一気に変換したほうが操作回数を減らせます。そこで各マスの色の変換は最大 1 回という条件で ③ が可能な最大数を求めます。隣り合うものをできるだけ反転し、残ったものだけ個別に反転するという作戦です。
超頂点 S から行番号と列番号の和が偶数であるマス（偶数マス）へ容量 1 の辺を張り、行番号と列番号の和が奇数（奇数マス）であるマスから超頂点 T へ容量 1 の辺を張ります。
偶数マスと隣り合う奇数マスが異なる色で両方とも色を変えなければならないマスのペアが見つかったら偶数マスから奇数マスへ容量 1 の辺を張ります。
超頂点 S から超頂点 T へフローを流して最大マッチングを求めます。マッチングした辺の両端の頂点であるマスは操作 ③ で変換されるマスなのでグリッド 1 のマスの色を実際に塗り替えます。この結果とグリッド 2 を比較して色が異なるマスは操作 ① または ② が必要なマスです。あとは操作した回数を数えてその回数を解として出力します。
|
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 |
using AtCoder; class Program { static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int H, int W) = (hw[0], hw[1]); int[,] grid1 = new int[H, W]; for (int r = 0; r < H; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < W; c++) grid1[r, c] = vs[c]; } int[,] grid2 = new int[H, W]; for (int r = 0; r < H; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < W; c++) grid2[r, c] = vs[c]; } AtCoder.MfGraph<int> G = new MfGraph<int>(H * W + 2); int s = H * W; int t = H * W + 1; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if ((r + c) % 2 == 0) { G.AddEdge(s, r * W + c, 1); if (r - 1 >= 0 && grid1[r, c] != grid1[r - 1, c] && grid1[r, c] != grid2[r, c] && grid1[r - 1, c] != grid2[r - 1, c]) { G.AddEdge(r * W + c, (r - 1) * W + c, 1); } if (r + 1 < H && grid1[r, c] != grid1[r + 1, c] && grid1[r, c] != grid2[r, c] && grid1[r + 1, c] != grid2[r + 1, c]) { G.AddEdge(r * W + c, (r + 1) * W + c, 1); } if (c - 1 >= 0 && grid1[r, c] != grid1[r, c - 1] && grid1[r, c] != grid2[r, c] && grid1[r, c - 1] != grid2[r, c - 1]) { G.AddEdge(r * W + c, r * W + c - 1, 1); } if (c + 1 < W && grid1[r, c] != grid1[r, c + 1] && grid1[r, c] != grid2[r, c] && grid1[r, c + 1] != grid2[r, c + 1]) { G.AddEdge(r * W + c, r * W + c + 1, 1); } } else G.AddEdge(r * W + c, t, 1); } } int ans = G.Flow(s, t); // 操作 ③ が必要な回数が確定する // マッチングしたマスの色を塗り替える var edges = G.Edges(); foreach (var edge in edges) { if (edge.Flow == 1 && edge.From != s && edge.To != t) { grid1[edge.From / W, edge.From % W] ^= 1; grid1[edge.To / W, edge.To % W] ^= 1; } } // 操作 ③ では色が同じになっていないマスの個数を数える for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid1[r, c] != grid2[r, c]) ans++; } } Console.WriteLine(ans); } } |
H – Maxmin Tour
問題の概要
N 頂点 M 辺の単純連結無向グラフがある。
A[1] から A[2]、A[2] から A[3]、…、A[K – 1] から A[K] と移動したい。
S[i] を 地点 A[i] から A[i + 1] までに移動した道のりと定義し、S の最大値をできるだけ小さくしたい。Q 個の魔法の石があり、それぞれ 1 回だけ使うことができる。
魔法の石を使うと地点 B[i] へワープすることができ、ワープ中に移動した道のりは 0 として記録される。魔法の石をうまく活用して S の最大値を最小化したい。その最小値を求めよ。
最大値を最小化したいときは二分探索法が有効です。S の最大値を val 以下にできるかという評価関数 Check(val) を定義することを考えます。
そのまえに魔法の石を使わずに地点 r から 地点 c までの道のりを計算して二次元配列にまとめておきます。これは重み付きの無向グラフの最短経路長を求める処理なのでダイクストラ法を採用しています。これで各頂点を始点としたときのすべての頂点への最短経路長をすべて取得することができます。
評価関数 Check(val) を定義することを考えます。
A[i] から A[i + 1] の最短経路長が val よりも長いときは魔法の石を使うしかありません。B[j] から A[i + 1] の最短経路長が v 以下である場合は魔法の石 j を使えば移動可能なので頂点 A[i] と 頂点 N + B[j] をマッチングさせてみます。最大マッチングが魔法の石を使わなければならない A の個数と一致する場合は、魔法の石を適切に選べば S の最大値を val 以下にできることを意味しています。
評価関数 Check(val) を定義することができたらあとは二分探索するだけです。
|
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 99 100 101 102 103 104 105 106 107 108 109 110 111 |
using AtCoder; class Program { static long[] Dijkstra(List<(int, long)>[] G, int start) { int v_cnt = G.Length; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); long[] dists = new long[v_cnt]; Array.Fill(dists, long.MaxValue); bool[] seen = new bool[v_cnt]; pq.Enqueue(start, 0); dists[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var edge in G[cur]) { if (dists[edge.Item1] > dists[cur] + edge.Item2) { dists[edge.Item1] = dists[cur] + edge.Item2; pq.Enqueue(edge.Item1, dists[cur] + edge.Item2); } } } return dists; } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M) = (nm[0], nm[1]); (int, int, int)[] UVW = new (int, int, int)[M]; for (int i = 0; i < M; i++) { int[] uvw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); UVW[i] = (uvw[0] - 1, uvw[1] - 1, uvw[2]); } int K = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_) - 1).ToArray(); int Q = int.Parse(Console.ReadLine()); int[] B = new int[0]; if (Q > 1) B = Console.ReadLine().Split().Select(_ => int.Parse(_) - 1).ToArray(); List<(int, long)>[] G1 = new List<(int, long)>[N]; for (int i = 0; i < N; i++) G1[i] = new List<(int, long)>(); for (int i = 0; i < M; i++) { G1[UVW[i].Item1].Add((UVW[i].Item2, UVW[i].Item3)); G1[UVW[i].Item2].Add((UVW[i].Item1, UVW[i].Item3)); } long[,] dists = new long[N, N]; for (int r = 0; r < N; r++) { long[] res = Dijkstra(G1, r); for (int c = 0; c < N; c++) dists[r, c] = res[c]; } long ok = (long)int.MaxValue * N; long ng = -1; long ans = StlFunction.BinarySearch(ok, ng, mid => Check(mid)); Console.WriteLine(ans); bool Check(long val) { AtCoder.MfGraph<int> G2 = new MfGraph<int>(N * 2 + 2); int s = N * 2; int t = N * 2 + 1; int cnt = 0; for (int i = 0; i + 1 < K; i++) { // 普通に A[i] から A[i + 1] 移動しようとするとできない if (dists[A[i], A[i + 1]] > val) { cnt++; // A[i] から B[?] へワープして B[?] から A[i + 1] へなら移動できる場合 foreach (var b in B) { if (dists[b, A[i + 1]] <= val) G2.AddEdge(A[i], N + b, 1); } } } for (int i = 0; i < N; i++) { G2.AddEdge(s, i, 1); G2.AddEdge(i + N, t, 1); } return G2.Flow(s, t) == cnt; } } } |
B69 – Black Company 2
問題の概要
ある工場には N 人の社員が在籍している。
社員 i が j 時台 (0 ≦ j ≦ 23) に働けるときは C[i, j] == ‘1’、そうでないときは C[i, j] == ‘0’ である。社員をあまりに働かせると、ブラック企業という評価を受けてしまうため、どの社員も一日 10 時間までしか勤務させることはできない。
このような条件下で、どの時間帯にも M 人以上が勤務しているようにシフトを組むことは可能だろうか？
社員を表す頂点を N 個、時間を表す頂点を 24 個、超頂点 S, T を用意します。
それぞれの社員は 10 時間までなら働かせてよいので、超頂点 S から社員を表す頂点に対して容量 10 の辺を張ります。社員を表す頂点から働ける時間を表す頂点に容量 1 の頂点を張ります。どの時間帯も M 人以上が勤務していないといけないので時間を表す頂点から超頂点 T へ容量 M の辺を張ります。
超頂点 S から T へフローを流して最大流を求めます。最大流が M の 24倍であれば条件にあうシフトを組むことは可能です。それ未満である場合は不可能です。
|
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 |
using AtCoder; class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M) = (nm[0], nm[1]); AtCoder.MfGraph<int> G = new MfGraph<int>(24 + N + 2); int s = N + 24; int t = N + 24 + 1; for (int i = 0; i < N; i++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < 24; c++) { if (vs[c] == '1') G.AddEdge(i, N + c, 1); } G.AddEdge(s, i, 10); } for (int i = 0; i < 24; i++) { G.AddEdge(i + N, t, M); } int frow = G.Flow(s, t); Console.WriteLine(frow == 24 * M ? "Yes" : "No"); } } |
