ひとりで勝手にはじめた蟻本読書会 グラフ理論 最短路問題 ダイクストラ法 蟻本読書会の続きです。
Contents
最小全域木問題とクラスカル法
最小全域木とは、グラフが連結であるという条件を保ったまま辺を消去して得られる木のなかで辺のコストの総和が最小となるもののことです。これを求めるのが最小全域木問題です。
最小全域木問題を解く方法にクラスカル法があります。
クラスカル法は、グラフの辺を（1）コストが小さい順に、（2）閉路を作らないように採用していくという方法です。グラフの辺を採用したときに閉路ができるかどうかはどうやって調べればよいでしょうか？ すでにつながっている頂点同士のあいだを辺でつなぐと必ず閉路ができます。
すでにつながっている頂点同士かどうかは前述のUnion-Find 木を使えばわかります。
基本問題
F – 最小全域木問題
N個の街があり、0, 1, 2, …, N – 1 と番号がついています。最初、これらの街の間に道はなく、街と街を行き来することはできません。
道の候補が M 個あります。i 番目の道を建設するには建設費が c_i 円かかりますが、建設すると街 u_i と街 v_i を双方向に結ぶ道ができ、行き来できるようになります。
M個の道の候補からいくつか選んで建設し、ある街から別の任意の街へ道をたどって到達できるようにしたいです。そのように道を選んで建設するために必要な建設費の最小値を求めてください。
入力されるデータ
N M
u_0 v_0 c_0
u_1 v_1 c_1
…
u_M-1 v_M-1 c_M-1（ただし
1 ≦ N ≦ 10^5
0 ≦ M ≦ 10^5
0 ≦ c_i ≦ 10^9）
UnionFindTreeクラスの定義は データ構造 Union-Find 木 蟻本読書会 と同じです。
Edgeクラスを定義して、2つの頂点とコストに関する情報を持たせます。入力されたデータからEdgeオブジェクトを生成したらコストが低い順にソートします。
UnionFindTree.IsSameメソッドで各辺のふたつの頂点はすでに同じグループか調べ、同じならこの辺を追加すると閉路ができるのでスキップします。閉路ができない場合はUnionFindTree.Uniteメソッドで同じグループに併合して求める総コストに Edge.Cost を加算します。辺のコストと頂点数から総コストはint型の範囲内には収まらないかもしれない点に注意すればあとは難しくない問題です。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Edge { public Edge(int v1, int v2, int cost) { Vertex1 = v1; Vertex2 = v2; Cost = cost; } public int Vertex1 { get; } public int Vertex2 { get; } public int Cost { get; } } class UnionFindTree { int[] parents = { }; // データxの親 // 引数は頂点の数 public UnionFindTree(int n) { parents = new int[n]; for (int i = 0; i < n; i++) parents[i] = i; // 最初はデータxの親は自分自身である } // データxが属する木の根を再帰で得る public int GetRoot(int x) { if (parents[x] == x) return x; parents[x] = GetRoot(parents[x]); return parents[x]; } // xとyの木を併合 public void Unite(int x, int y) { int rx = GetRoot(x); //xの根 int ry = GetRoot(y); //yの根 // xとyの根が同じ(=同じ木にある)時はそのまま //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける if (rx != ry) parents[rx] = ry; } // 2つのデータx, yが属する木が同じならtrueを返す public bool IsSame(int x, int y) { int rx = GetRoot(x); int ry = GetRoot(y); return rx == ry; } } class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } List<Edge> edges = new List<Edge>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0]; int b = vs[1]; int cost = vs[2]; edges.Add(new Edge(a, b, cost)); } edges = edges.OrderBy(_ => _.Cost).ToList(); // コストが低い順にソート UnionFindTree uft = new UnionFindTree(N); long ans = 0; foreach(Edge edge in edges) { if (uft.IsSame(edge.Vertex1, edge.Vertex2)) continue; uft.Unite(edge.Vertex1, edge.Vertex2); ans += edge.Cost; } Console.WriteLine(ans); } } |
応用問題
D – Game on a Grid
縦の長さが H、横の長さが W であるような H×W 個のマスからなる二次元盤面があります。 この盤面の左から
x(1 ≦ x ≦ W) 、上から y(1 ≦ y ≦ H) 番目にあるマスを、マス (x, y) と表します。各マスには、それぞれ非負整数が書かれており、マス (x, y) に書かれている数は P (x, y) です。
どの時点でもこの盤面上のどこかに居ます。そして、以下のようなルールに基づいて行動をします。
今いるマスから上下左右に隣り合うマスへ移動することができる。ただし、盤面から出てしまうような移動はできない。
あるマスに初めて訪れたとき、そのマスに書かれている数だけの得点を得る。
今いるマスからまだ訪れていないマスに移動するとき、移動ボーナスとして、(今いるマスに書かれている数)×(次に訪れるマスに書かれている数) だけの得点を得る。
既に訪れているマスへ移動するときには、得点は生じない。最初スタート地点であるマス (S_x ,S_y) に訪れます。ルールに基づいて自由に行動し、最終的にゴール地点であるマス (G_x ,G_y) に訪れ行動を終えたいと思っています。 一度ゴール地点に訪れた後、行動を終了せず、再びゴール地点に戻ってきてもよいことに注意してください。
ルールに基づいて行動し達成することのできる最大の合計得点を出力してください。
入力されるデータ
H W
S_x S_y
G_x G_y
P (1,1) P (2,1) … P (W,1)
P (1,2) P (2,2) … P (W,2)
…
P (1,H) P (2,H) … P (W,H)（ただし、
1 ≦ H, W ≦ 100, 1 ≦ P (x, y) ≦ 100
1 ≦ S_x, G_x ≦ W, 1 ≦ S_y, G_y ≦ H）
初めて訪問したときだけ点が加算されるのでその部分だけを辺として考えます。コストはマスに書かれている数の積です。またボーナス点だけでなく訪問時の加算点もあり、減点はないのですべてのマスを訪問したほうがよいことになります。
そのため全体を辺でつなぐことになります。最小全域木問題ではコストを最小にすることを考えましたが、ここでは最大にすることを考えます。最小全域木問題ならぬ最大全域木問題です。出発点とゴール地点が指定されていますが、同じマスを何度でも通ることができるので関係ありません。ただ最大全域木問題を解けばよいという問題です。
頂点に0からはじまる通し番号をつけますが、これは0から開始する行番号と列番号から算出される値を使います。中点番号は（行番号 * 幅 + 列番号）です。横につながっているマスと縦につながっているマスの数の積からコストを算出して最大全域木問題を解きます。
|
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 System; using System.Collections.Generic; using System.Linq; // EdgeクラスとUnionFindTreeクラスの定義は同じなので省略 class Program { static void Main() { int H, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } int sx, sy; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); sx = vs[0] - 1; sy = vs[1] - 1; } int gx, gy; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); gx = vs[0] - 1; gy = vs[1] - 1; } int[,] P = new int[W, H]; int sum = 0; for (int row = 0; row < H; row++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int col = 0; col < W; col++) { P[col, row] = vs[col]; sum += vs[col]; } } List<Edge> edges = new List<Edge>(); for (int row = 0; row < H; row++) { for (int col = 0; col < W - 1; col++) { int vnum1 = row * W + col; int vnum2 = row * W + col + 1; edges.Add(new Edge(vnum1, vnum2, P[col, row] * P[col + 1, row])); } } for (int col = 0; col < W; col++) { for (int row = 0; row < H - 1; row++) { int vnum1 = row * W + col; int vnum2 = (row + 1) * W + col; edges.Add(new Edge(vnum1, vnum2, P[col, row] * P[col, row + 1])); } } edges = edges.OrderByDescending(_ => _.Cost).ToList(); UnionFindTree uft = new UnionFindTree(W * H); long ans = sum; foreach(Edge edge in edges) { if (uft.IsSame(edge.Vertex1, edge.Vertex2)) continue; uft.Unite(edge.Vertex1, edge.Vertex2); ans += edge.Cost; } Console.WriteLine(ans); } } |
D – Built?
平面上に N 個の街があります。i 個目の街は、座標 (x_i ,y_i) にあります。同じ座標に、複数の街があるかもしれません。
座標 (a, b) にある街と座標 (c, d) にある街の間に道を造るのには、min(|a – c|, |b – d|) 円かかります。街と街の間以外に、道を造ることはできません。
任意の 2 つの街の間を、道を何本か通って行き来できるようにするためは、最低で何円必要でしょうか。
入力されるデータ
N
x_1 y_1
x_2 y_2
…
x_N x_N（ただし
2 ≦ N ≦ 10^5
0 ≦ x_i, y_i ≦ 10^9）
これも最小全域木問題でありクラスカル法で解くことができます。といってもすべての街をつなぐためのコストを事前に計算することはできません。そこで必要な辺だけに限定して考えます。
コストは X 座標の差の絶対値と Y 座標の差の絶対値の小さい方であるということに注目します。すると明らかに無駄な計算を省略することができます。
街の座標を X 座標でソートすると隣り合った頂点間の辺しか使われないことに気づきます。Y 座標でソートした場合も同じです。それぞれでソートして街をつなぐコストを計算します。X 座標でソートした場合とY 座標でソートした場合の結果である（N – 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 |
using System; using System.Collections.Generic; using System.Linq; // EdgeクラスとUnionFindTreeクラスの定義は同じなので省略 class Position { public Position(int index, int x, int y) { X = x; Y = y; Index = index; } public int Index { get; } public int X { get; } public int Y { get; } } class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<Position> positions = new List<Position>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0]; int b = vs[1]; positions.Add(new Position(i, a, b)); } List<Edge> edges = new List<Edge>(); // X 座標でソートして隣の要素とのコストだけ取得して辺をつくる positions = positions.OrderBy(_ => _.X).ToList(); for (int i = 0; i < positions.Count - 1; i++) { int dx = Math.Abs(positions[i].X - positions[i + 1].X); int dy = Math.Abs(positions[i].Y - positions[i + 1].Y); int cost = Math.Min(dx, dy); edges.Add(new Edge(positions[i].Index, positions[i + 1].Index, cost)); } // Y 座標でソートして隣の要素とのコストだけ取得して辺をつくる positions = positions.OrderBy(_ => _.Y).ToList(); for (int i = 0; i < positions.Count - 1; i++) { int dx = Math.Abs(positions[i].X - positions[i + 1].X); int dy = Math.Abs(positions[i].Y - positions[i + 1].Y); int cost = Math.Min(dx, dy); edges.Add(new Edge(positions[i].Index, positions[i + 1].Index, cost)); } // 最小全域木のコストを計算する edges = edges.OrderBy(_ => _.Cost).ToList(); UnionFindTree uft = new UnionFindTree(N); long ans = 0; foreach (Edge edge in edges) { if (uft.IsSame(edge.Vertex1, edge.Vertex2)) continue; uft.Unite(edge.Vertex1, edge.Vertex2); ans += edge.Cost; } Console.WriteLine(ans); } } |
E – Clique Connect
N 頂点からなる重み付き無向グラフ G があります。 G の各頂点には 1 から N までの番号が付けられています。 最初、G には辺が 1 本も存在しません。
今から、M 回の操作を行うことによって G に辺を追加していきます。
i (1 ≦ i ≦ M) 回目の操作は以下の通りです。
K_i 個の頂点からなる頂点の部分集合 S_i = { A[i, 1], A[i, 2], … A[i, K_i] } が与えられる。
u, v ∈ S_i かつ u ＜ v を満たす全ての u, v について、頂点 u と頂点 v の間に重み C_i の辺を追加する。M 回の操作を全て行ったとき G が連結になるか判定し、連結になるならば G の最小全域木に含まれる辺の重みの総和を、連結にならないならば -1 を出力せよ。
入力されるデータ
N M
K_1 C_1
A[1, 1], A[1, 2], … A[1, K_1]
K_2 C_2
A[2, 1], A[2, 2], … A[2, K_2]K_M C_M
A[M, 1], A[M, 2], … A[M, K_M]（ただし、
2 ≦ N ≦ 2 × 10^5
1 ≦ M ≦ 2 × 10^5
2 ≦ K_i ≦ N （総和は 4 × 10^5 を超えない）
1 ≦ A[i, 1] ＜ A[i, 2] ＜ … ＜ A[i, K_i] ≦ N
1 ≦ C_i ≦ 10^9 ）
問題文には、K_i 個の頂点からなる頂点の部分集合 S_i = { A[i, 1], A[i, 2], … A[i, K_i] } が与えられる。これらの間に重み C_i の辺を追加せよとあります。しかし G の隣接リストを生成するさいにこんなことをしていては制限時間に間に合いません。
最小全域木に含まれる辺の重みの総和が変わらないのであれば無視することができるものがあるのであれば処理を省略することができます。では最小全域木に含まれる辺の重みの総和が変わらない辺とはどのような辺なのでしょうか？
頂点 u と頂点 v を直接結ぶ辺を e = (u, v) とします。するとすでに頂点 u と頂点 v を結ぶパスが存在し、パスを構成する辺のそれぞれの重みが e の重み以下である場合、e はなくても最小全域木に含まれる辺の重みの総和はかわりません。
クラスカル法の動作では辺の重みが小さいものから辺を追加するかどうかを判断しますが、辺 e を追加するかどうかを判断するときには u, v は既に連結になっているので、辺 e が追加されることはないのです。
そのため、与えられた K_i 個の頂点からなる頂点の部分集合 S_i = { A[i, 1], A[i, 2], … A[i, K_i] } のなかで辺を追加する処理が必要なのは、A[i, 1] と A[i, j] （ただし、2 ≦ j ≦ K_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 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 112 |
using System; using System.Collections.Generic; using System.Linq; // UnionFindTreeクラスの定義は同じなので省略 class Edge { public Edge(int from, int to, int cost) { From = from; To = to; Cost = cost; } public int From = 0; public int To = 0; public int Cost = 0; } class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } // G が連結になるか判定するための隣接リストをつくる List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); // 最小全域木問題を解くために辺オブジェクトのリストを格納する List<Edge> edges = new List<Edge>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int k = vs[0]; int c = vs[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // こんなことをしていては間に合わない // for (int x = 0; x < A.Length; x++) // { // for (int y = x + 1; y < A.Length; y++) // { // int a = A[x] - 1; // int b = A[y] - 1; // list[a].Add(b); // list[b].Add(a); // edges.Add(new Edge(a, b, c)); // edges.Add(new Edge(b, a, c)); // } // } for (int x = 1; x < A.Length; x++) { // 隣接リストに追加するのは A[0] とその他の頂点間の辺だけでOK int a = A[0] - 1; int b = A[x] - 1; list[a].Add(b); list[b].Add(a); edges.Add(new Edge(a, b, c)); edges.Add(new Edge(b, a, c)); } } // G が連結になるか判定する（頂点 0 からそれ以外の頂点にたどり着けるか？） bool[] ischeck = new bool[N]; Queue<int> queue = new Queue<int>(); ischeck[0] = true; queue.Enqueue(0); while (queue.Count > 0) { int cur = queue.Dequeue(); foreach (int next in list[cur]) { if (ischeck[next]) continue; ischeck[next] = true; queue.Enqueue(next); } } // G が連結ではない場合は -1 を出力して終了 if (ischeck.Any(_ => _ == false)) { Console.WriteLine(-1); return; } // G が連結であることがわかったので最小全域木の辺の重みの総和を計算する UnionFindTree tree = new UnionFindTree(N); edges = edges.OrderBy(_ => _.Cost).ToList(); long ans = 0; foreach (Edge edge in edges) { if (tree.IsSame(edge.From, edge.To)) continue; tree.Unite(edge.From, edge.To); ans += edge.Cost; } Console.WriteLine(ans); } } |
