AtCoder NoviStepsを埋めてみる(20) SortedSet 1Qの続きです。今回は重みつきUnion-Find（別名 ポテンシャル付き Union-Find）です。
Contents
重みつきUnion-Find（ポテンシャル付き Union-Find）とその実装
普通の Union-Find は
① Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
② Union: 2つの集合を1つに統合する。
でしたが、重みつきUnion-Find はこれを少し発展させて、各ノード v に重み weight(v) を持たせ、ノード間の距離も管理するようなものになっています。これによって「A は B より 3 大きい」「B は C より 2 大きい」というふたつの情報から「A は C より どれだけ大きいか？」という問いにほぼ定数時間で答えることができます。また「A は B より 3 大きい」「B は C より 2 大きい」から「A は C より 10 大きい」という 3 つの条件があるとき、実はこれらは矛盾しているのですが、このような矛盾の有無を確認するときにも使えます。
重みつきUnion-Find の主な機能としては以下の 3 つがあります。
merge： weight(y) = weight(x) + w となるように x と y を merge する
same： x と y は同じグループにいるかどうかの判定
diff： x と y の重みの差を返す
|
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 |
public class WeightedUnionFind { int[] Leaders; // 各頂点の代表（各頂点の親をたどっていったときにたどりつく頂点）を格納する long[] Diffs; // 各頂点の重み（親ノードとの値の差分） public WeightedUnionFind(int n) { Leaders = new int[n]; Diffs = new long[n]; for (int i = 0; i < n; ++i) { Leaders[i] = i; Diffs[i] = 0; } } // 再帰処理で頂点 x の代表を求める。 // 毎回何度も再帰処理をしていると時間がかかるので Leaders[x] に結果を代入して次回以降は O(1)で取得できるようにする（経路圧縮） // 経路圧縮とともに差分重み Diffs も更新している public int Leader(int x) { if (Leaders[x] == x) { return x; } else { int r = Leader(Leaders[x]); Diffs[x] += Diffs[Leaders[x]]; Leaders[x] = r; return Leaders[x]; } } // 頂点 x と y は同一グループか？ Leader(x) == Leader(y) なら同一グループである。 public bool IsSame(int x, int y) { return Leader(x) == Leader(y); } // x と y を merge するとともに 重みの差が w になるようにする public bool Merge(int x, int y, long w) { // 引数の矛盾をチェック（すでにmergeされていて Diff(x, y) == w でないなら矛盾している） if (IsSame(x, y)) return Diff(x, y) == w; // ふたつの頂点 x, y の代表を取得して y の代表を x の代表とする int xLeader = Leader(x); int yLeader = Leader(y); // x と y の重みの差が w になるように引数を補正する w += Diffs[x]; w -= Diffs[y]; Leaders[yLeader] = xLeader; Diffs[yLeader] = w; return true; } // 頂点 x, y の重みの差を返す public long Diff(int x, int y) { // 経路圧縮したあと Diffs[y] - Diffs[x] を返す _ = Leader(x); _ = Leader(y); return Diffs[y] - Diffs[x]; } } |
D – Hidden Weights
問題の概要
N 頂点 M 辺の有向グラフが与えられる。
各頂点に -10^18 以上 10^18 以下の整数を書き込む方法であって、次の条件を満たすものを 1 つ出力せよ。
（条件）頂点 i に書き込まれている値を X[i] としたとき、すべての辺 j = 1, 2, …, M について X[v[j]] – X[u[j]] = w[j] が成り立つ。
同じ連結成分であれば 1 つの頂点の値が決まるとすべて決まります。このようなときに 重みつきUnion-Find が役に立ちます。
|
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 |
// WeightedUnionFind クラスは上記定義のとおり class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; WeightedUnionFind tree = new WeightedUnionFind(N); for (int i = 0; i < M; i++) { int[] uvw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int u = uvw[0] - 1; int v = uvw[1] - 1; int w = uvw[2]; tree.Merge(u, v, w); } List<long> ans = new List<long>(); for (int i = 0; i < N; i++) { long v = tree.Diff(0, i); ans.Add(v); } Console.WriteLine(string.Join(" ", ans)); } } |
D – Relative Position
問題の概要
座標平面上に 1 から N の番号がついた N 人の人がいる。
人 1 は原点にいる。
次の形式の情報が M 個与えられる。
人 A[i] から見て、人 B[i] は、x 軸正方向に X[i]、y 軸正方向に Y[i] 離れた位置にいる。
それぞれの人がいる座標を求めよ。一意に定まらないときはその旨報告せよ。
XY 座標平面上なので X 成分と Y 成分にわけて考えます。WeightedUnionFind をふたつ生成すればよいです。
人 1 とX 成分と Y 成分の少なくともどちらかが同一連結成分に属するのであれば 人 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 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; WeightedUnionFind treeX = new WeightedUnionFind(N); WeightedUnionFind treeY = new WeightedUnionFind(N); for (int i = 0; i < M; i++) { int[] abxy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = abxy[0] - 1; int b = abxy[1] - 1; int x = abxy[2]; int y = abxy[3]; treeX.Merge(a, b, x); treeY.Merge(a, b, y); } List<long> ans = new List<long>(); for (int i = 0; i < N; i++) { long x = treeX.Diff(0, i); long y = treeY.Diff(0, i); if (treeX.IsSame(0, i) || treeY.IsSame(0, i)) Console.WriteLine($"{x} {y}"); else Console.WriteLine("undecidable"); } } } |
D – People on a Line
問題の概要
x 軸上に N 人の人が立っている。人 i の位置を X[i]（X[i] は 0 以上 10^9 以下の整数）とする。
同じ位置に複数の人が立っていることもありうる。
人 R[i] は人 L[i] よりも距離 D[i] だけ右にいるという情報が M 個与えられる。
与えられる M 個すべての情報に矛盾があるかどうか判定せよ。
入力を WeightedUnionFind.Merge メソッドで merge していけばよいです。途中で矛盾があれば false が返されるので矛盾を検出することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; WeightedUnionFind tree = new WeightedUnionFind(N); bool yes = true; for (int i = 0; i < M; i++) { int[] lrd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int l = lrd[0] - 1; int r = lrd[1] - 1; int d = lrd[2]; if (!tree.Merge(l, r, d)) yes = false; } Console.WriteLine(yes ? "Yes" : "No"); } } |
F – Good Set Query
問題の概要
Q 個の整数の 3 つ組 (A[i], B[i], D[i]) が与えられる。
集合 {1, 2, …, Q} の部分集合 S が良い集合であることを、下記の条件を満たす長さ N の整数列 X が存在することと定める。
すべての i ∈ S について X[A[i]] – X[B[i]] = D[i] が成り立つ。
S が空集合である状態から始め、i = 1, 2, …, Q の順に下記の操作をおこなう。
もし S∪{i} が良い集合なら、S を S∪{i} で置き換える。
最終的な S のすべての要素を昇順に出力せよ。
i 番目の入力がこれまでのものと矛盾していないなら i を S に追加します。矛盾しているときは無視します（merge の処理をおこなわない）。
最後に S を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int Q = nm[1]; WeightedUnionFind tree = new WeightedUnionFind(N); List<int> ans = new List<int>(); for (int i = 0; i < Q; i++) { int[] abd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = abd[0] - 1; int b = abd[1] - 1; int d = abd[2]; if (tree.Merge(a, b, d)) ans.Add(i + 1); } Console.WriteLine(string.Join(" ", ans)); } } |
F – Pay or Receive
問題の概要
1, …, N の番号がついた N 個の街と、1, …, M の番号がついた M 本の道路がある。
道路 i は街 A[i] と B[i] を結んでいて、A[i] から街 B[i] に移動するときにはポイントが C[i] だけ増加し、逆向きに移動すると C[i] だけ減少する。
所持しているポイントは負にもなりえる。
次の Q 個の質問に答えよ。
（質問）所持しているポイントが 0 である状態で街 X[i] から移動を始めたとき、街 Y[i] にいる状態で所持しているポイントの最大値を出力せよ。
ただし、街 X[i] から街 Y[i] に到達できないときは nan、街 Y[i] にいる状態で所持しているポイントをいくらでも増やせるときは inf を出力せよ。
閉路がない場合、WeightedUnionFind で道路で街同士を merge して Diff を取得すればそれが解となります。
閉路がある場合で、閉路を回り続けることでポイントをいくらでも増やせるときは inf が解となります。
閉路を回り続けることでポイントをいくらでも増やせるかを調べる方法ですが、まず重みの絶対値で降順ソートします。重みの絶対値が大きい順に merge していくのですが、このとき矛盾があればそこを回り続けることでポイントをいくらでも増やせる閉路があるということなので、その頂点の Leader を取得して保存しておきます。
質問に答えるときに X[i] と Y[i] が同一連結成分に属し、X[i] の Leader が保存しておいた頂点と一致するときは inf が解となります。そうでない場合は Diff(X[i], Y[i]) が解です。また tree.IsSame(X[i], Y[i]) == false のときは同一成分内に存在しないということなので、街 X[i] から街 Y[i] には到達できず nan が解となります。
|
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 |
class Program { static void Main() { int[] nmq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nmq[0]; int M = nmq[1]; int Q = nmq[2]; List<(int, int, int)> tps = new List<(int, int, int)>(); for (int i = 0; i < M; i++) { int[] abc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = abc[0] - 1; int b = abc[1] - 1; int c = abc[2]; tps.Add((a, b, c)); } tps = tps.OrderByDescending(_ => Math.Abs(_.Item3)).ToList(); WeightedUnionFind tree = new WeightedUnionFind(N); HashSet<int> set = new HashSet<int>(); // ここを通ると無限増殖 foreach (var tp in tps) { int a = tp.Item1; int b = tp.Item2; int c = tp.Item3; if (!tree.Merge(a, b, c)) set.Add(tree.Leader(a)); } for (int i = 0; i < Q; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0] - 1; int y = xy[1] - 1; if (!tree.IsSame(x, y)) Console.WriteLine("nan"); else if (set.Contains(tree.Leader(x))) Console.WriteLine("inf"); else Console.WriteLine(tree.Diff(x, y)); } } } |
