ABC 087 D - People on a Line
ぱっと問題を見てUnion-Findを使えばよさそうというところまでは辿りついたが、実装に手間どってしまった。 通常のUnion Findはノードのルートノードを管理するが、今回はそれに加えて、ルートノードからの距離を管理すればよい。たとえば次のように2つのテーブルを用意して、「ノード2のルートノードはノード0で、ノード2はルートノードから距離2のところにある」と解釈する。
table:root
0 1 2
0 1 0
table:delta
0 1 2
0 0 2
あとは、union(x, y, dist) のときに、このテーブルを正しく更新すればよい。ここでxのルートへ、yのルートをマージするとすると（逆の場合はxとyを入れ替えてdistに負の符号をつければよい）rootテーブルの方は単純にyのルートの値をxのルートにすればよい。
一方deltaテーブルの方はすこしややこしくて、xからyまでの距離を$ d、xのルートからxまでの距離を$ \Delta x、yのルートからyまでの距離を$ \Delta y、xのルートからyのルートまでの距離を$ \Delta y_{\text{root}}とすると、与えられた情報から$ \Delta y_{\text{root}}を計算すればよい。yの位置を考えると$ \Delta y_{\text{root}} + \Delta y = \Delta x + dがなりたつから$ \Delta y_{\text{root}} = \Delta x + d - \Delta yと計算できる。
あとは通常のUnion Findと同様に持ち上げやランクを使って最適化する。解説はグラフ問題に帰着していた。 code:java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
UnionFind uf = new UnionFind(N);
for (int i = 0; i < M; i++) {
int left = scanner.nextInt() - 1;
int right = scanner.nextInt() - 1;
int dist = scanner.nextInt();
Result lr = uf.find(left);
Result rr = uf.find(right);
if (lr.root == rr.root) {
if (rr.dist - lr.dist != dist) {
System.out.println("No");
return;
}
} else {
uf.union(left, right, dist);
}
}
System.out.println("Yes");
}
static class UnionFind {
private final int[] table;
private final int[] delta;
private final int[] ranks;
UnionFind(int size) {
this.table = new intsize; this.delta = new intsize; this.ranks = new intsize; for (int i = 0; i < size; i++) tablei = i; }
Result find(int x) {
Result res = find(tablex); }
return new Result(tablex, deltax); }
void union(int x, int y, int dist) {
Result xRoot = find(x);
Result yRoot = find(y);
if (xRoot.root == yRoot.root) return;
Result tmp = xRoot;
xRoot = yRoot;
yRoot = tmp;
dist = -dist;
}
}
}
static class Result {
public final int root;
public final int dist;
Result(int root, int dist) {
this.root = root;
this.dist = dist;
}
}
}