AtCoder NoviStepsを埋めてみる(30) 最大流・最小カット問題 1D 2Dの続きです。今回は燃やす埋める問題です。
燃やす埋める問題とは？
燃やす埋める問題とは以下のような問題です。
N 個のゴミがある。それぞれのゴミを「燃やす」か「埋める」かで処分しなければならない。
ゴミ i を燃やすのに A[i] 円、埋めるのに B[i] 円かかる。また以下のルールが M 個ある。
ゴミ X[j] を燃やしてゴミ Y[j] を埋めると、罰金 Z[j] 円かかる。最小で何円必要だろうか？
これを最小カット問題で解きます。
まず、N + 2 個の頂点を用意します。頂点 i はゴミ i を表しています。残りの 2 つは超頂点 S, T です。
最小カット問題を解くと頂点が、S 側と T 側にわかれるので、超頂点 S を燃やす側、超頂点 T を埋める側とします。以下のように辺を張ります。
頂点 i から T へ辺を張ります。辺の容量はゴミ i を燃やしたときのコストとします。頂点 S から i へ辺を張ります。辺の容量はゴミ i を埋めたときのコストとします。これで最小カットを求めると頂点が S 側と T 側に分かれます。S 側の頂点が燃やすべきゴミで、T 側が埋めるべきゴミです。最小カットがコストの最小値です。
もうひとつ条件がありました。ゴミ X[j] を燃やしてゴミ Y[j] を埋めると、罰金 Z[j] 円かかるという条件です。頂点 X[j] から頂点 Y[j] へ容量 Z[j] の辺を張ります。これがゴミ X[j] を燃やしてゴミ Y[j] を埋めると、罰金 Z[j] 円かかることを表しています。
このように辺を張って S から T へフローを流して最小カットを求めると、すべてのゴミを処分するために必要な最小コストを得ることができます。
B68 – ALGO Express
問題の概要
N 個の駅がある。
このなかから 0 個以上を特急駅に指定したい。駅 i を特急駅に指定することで P[i] 円の利益が見込める。ただし、P[i] は負数である場合もありうる。
利用者から「駅 A[j] を特急駅に指定するならば、駅 B[j] も特急駅に指定するべきだ」という提案が M 個出されている。
これらの提案どおりにした場合、最大何円の利益を出すことができるだろうか？
最初の「燃やす埋める問題」の例ではコストを問題にしていましたが、この問題ではコストではなく報酬を問題にしています。これをコストの問題に変換します。
どのようにするかというと、P[i] の最大値は 150 なので先に 200 × N の報酬を先に受け取っていることにします。そして特急を停車させるさせないを決定することに伴う最小コストを差し引くことで解を得ることを考えます。
最初の「燃やす埋める」と同様に考えるなら辺の張り方は以下のようになります。
駅 i に停車させるコストは 200 – P[i]、停車させないコストは 200。
⇒ 頂点 i から 超頂点 T へ 容量 200 – P[i] の辺を張り、超頂点 S から 頂点 i へ 容量 200 の辺を張る。
駅 A[j] に停車させたにもかかわらず 駅 B[j] に停車させないことは許されないので、その場合は罰金 ∞ を科す。
⇒ 頂点 A[j] から 頂点 B[j] へ 容量 int.MaxValue の辺を張る。
これで超頂点 S から T へフローを流して最小カットを求めると最小コストが得られます。200 × N からこの最小コストを差し引いた値が求めるべき解です。
|
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 |
class Program { static void Main() { (int N, int M) = ReadInt2(); int[] P = ReadIntArray(); MfGraph<long> G = new MfGraph<long>(N + 2); int s = N; int t = N + 1; for (int i = 0; i < N; i++) { G.AddEdge(i, t, 200 - P[i]); G.AddEdge(s, i, 200); } for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; G.AddEdge(a, b, int.MaxValue); } long ans = 200 * N - G.Flow(s, t); Console.WriteLine(ans); } } |
040 – Get More Money（★7）
問題の概要
N 軒の家があり、家 i の中には、現金 A[i] 円と、K[i] 本の鍵（それぞれ家 C[i, 0], C[i, 1], …, C[i, K[i] – 1] の鍵）が置いてある。
家に入るときは料金 W 円を支払わなければならない。また家 i の鍵が他の家にあるときはすべての鍵を回収してからでないと家 i に入ることができない。家に入る手順をうまく決めたときに、最大で何円得するか求めよ。ただし移動の過程で所持金が負数になってもかまわないものとする。
これもコストではなく報酬を最大化する問題です。先にすべての家から 現金 A[i] 円 を回収したことにします。そして実際に 家 i を訪問するかしないかを決めて、訪問するなら料金 W 円を払って訪問し、訪問しないなら先に回収した A[i] 円を返金します。これらのコストを最小化することを考えます。
また家 i を訪問するためには鍵が置かれている家すべてを訪問しなければなりません。
家 i を訪問するコストは W、訪問しないコストは A[i]。
⇒ 頂点 i から超頂点 T へ容量 W の辺を張り、超頂点 S から頂点 i へ容量 A[i] の辺を張る。
家 x を訪問したにもかかわらず家 y を訪問しないのは許されないので罰金 ∞。
⇒ 頂点 x から頂点 y へ容量 int.MaxValue の辺を張る。
超頂点 S から T へフローを流して、最小カットを求めます。これがコストの最小値です。A.Sum() – コストの最小値が求めるべき解です。
|
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 |
using AtCoder; class Program { static void Main() { int[] nw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int W) = (nw[0], nw[1]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); MfGraph<long> G = new MfGraph<long>(N + 2); int s = N; int t = N + 1; for (int i = 0; i < N; i++) { G.AddEdge(i, t, W); G.AddEdge(s, i, A[i]); } // 鍵を持っていないのに訪問したら罰金 ∞ for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); vs = vs.Skip(1).Select(_ => _ - 1).ToArray(); foreach (int v in vs) G.AddEdge(v, i, int.MaxValue); // 家 v を訪問したのに 家 i は訪問しない } long flow = G.Flow(s, t); Console.WriteLine(A.Sum() - flow); } } |
G – Cascading Grid
問題の概要
H 行 W 列のグリッドがある。各マスには +, -, # のいずれか一文字が書かれている。
次の操作を 0 回以上行うことができる。
# でないマスを 1 つ選ぶ。「選んだマスから # のマスを通ることなく、隣接するマスへ左・右・下のいずれかの方向に移動することだけで到達できるマス」をすべて # に変える。ただし、選んだマス自身も到達できるマスに含まれる。
操作後のグリッドにおける、+ のマスの個数から – のマスの個数を引いた値としてあり得る最大値を求めよ。
「選んだマスから # のマスを通ることなく、隣接するマスへ左・右・下のいずれかの方向に移動することだけで到達できるマスをすべて # に変える」という操作をした場合、あるマスが # でないならその上にあるマスや左右にあるマスも # にはなりません（最初から # だった場合を除く）。
まず ‘+’ の個数を数えます。そしてここからコスト分を差し引いた値を求めます。
コストには残すコストと消すコストのふたつがあります。残すコストは ‘-‘ であれば 1、そうでないなら 0 です。消すコストは ‘+’ であれば 1、そうでなければ 0 です。
そこでマス (r, c) から超頂点 T へ残すコストを容量とする辺を張り、超頂点 S から頂点 i へ消すコストを容量とする辺を張ります。
マス (r, c) を残すのであればその上や左右にあるマスも残さなければなりません。消してしまったら罰金 ∞ なのでマス (r, c) からその上や左右にあるマスに向けて容量 int.MaxValue の辺を張ります。
超頂点 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 |
using AtCoder; 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]; long plus = 0; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) { grid[r, c] = vs[c]; plus += vs[c] == '+' ? 1 : 0; } } AtCoder.MfGraph<long> G = new AtCoder.MfGraph<long>(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++) { int idx = r * W + c; G.AddEdge(s, idx, grid[r, c] == '+' ? 1 : 0); // 消すコスト G.AddEdge(idx, t, grid[r, c] == '-' ? 1 : 0); // 残すコスト } } // 自分を残すのであれば上, 左右も残さなければならない // 自分を残して上, 左右を消したら罰金 for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { int idx = r * W + c; if (grid[r, c] != '#') { if (r - 1 >= 0 && grid[r - 1, c] != '#') { int u_idx = (r - 1) * W + c; G.AddEdge(idx, u_idx, int.MaxValue); } if (c - 1 >= 0 && grid[r, c - 1] != '#') { int l_idx = r * W + c - 1; G.AddEdge(idx, l_idx, int.MaxValue); } if (c + 1 < W && grid[r, c + 1] != '#') { int r_idx = r * W + c + 1; G.AddEdge(idx, r_idx, int.MaxValue); } } } } long flow = G.Flow(s, t); Console.WriteLine(plus - flow); } } |
E – MUL
問題の概要
宝石が N 個ある。
以下の操作を 0 回以上、好きなだけ行うことができる。
・正整数 x を選び、x の倍数が書かれた宝石をすべて叩き割る。i が書かれていた宝石が割られずに残っていた場合、A[i] 円貰うことができるが、この値は負数の場合がある。
もらえる金額の最大値を求めよ。
A[i] の絶対値は 10^9 なので先に 10^9 × N を受け取っておき、割った宝石の価値をコストとして差し引くことにします。
超頂点 S 側を壊す、T 側を壊さないとします。
そして以下のように辺を張ります。
宝石 i を壊すコストは 10^9、壊さないコストは 10^9 – P[i]
⇒ 宝石 i を壊すのであれば頂点 i から超頂点 T へ容量 10^9 の辺を張り、壊さないのであれば超頂点 S から頂点 i へ容量 10^9 – A[i] の辺を張る。
宝石 x を壊したにもかかわらず y を壊さない場合は罰金 ∞
⇒ 頂点 x から 頂点 y へ容量 int.MaxValue の辺を張る。
超頂点 S から T へフローを流して、最小カットを求めます。これがコストの最小値です。10^9 × N – コストの最小値が求めるべき解です。
|
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 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); MfGraph<long> G = new MfGraph<long>(N + 2); int s = N; int t = N + 1; for (int i = 0; i < N; i++) { G.AddEdge(i, t, (long)Math.Pow(10, 9)); G.AddEdge(s, i, (long)Math.Pow(10, 9) - A[i]); } // i を壊したにもかかわらずその整数倍を壊さない場合は罰金 ∞ for (int i = 0; i < N; i++) { int v = i + 1; for (int j = 2; j < 110; j++) { int next_v = v * j; if (next_v <= N) G.AddEdge(i, next_v - 1, int.MaxValue); else break; } } long flow = G.Flow(s, t); long ans = (long)Math.Pow(10, 9) * N - flow; Console.WriteLine(ans); } } |
