これも重み付き Union-Find で解ける問題!
問題概要
具体例として一つの入力ケースを示す。
7 1 kilometre = 10^3 metre 1 megametre = 10^3 kilometre 1 metre = 10^-6 megametre 1 terametre = 10^3 gigametre 1 petametre = 10^3 terametre 1 gigametre = 10^-6 petametre 1 metre = 10^-15 petametre
このように、 本の「単位換算式」が与えられる (上の例は )。これら単位換算式が矛盾を発生していないかどうかを判定せよ。
制約
- 左辺と右辺とで単位は異なる
- 同じ単位の組が 2 度以上登場することはない
- の指数 の値は 以上 以下の整数
解法 (1):重み付き Union-Find
重み付き Union-Find を知っていれば、それを使うだけで解ける問題だとわかる!!
重み付き Union-Find は、Union-Find の各ノードに重みを持たせたデータ構造であり、以下のクエリ処理をサポートできる。なお、この表では Union-Find のノード x
の重みを と表記している。
クエリ | 処理内容 |
---|---|
merge(x, y, w) |
となるように x と y を併合する |
issame(x, y) |
ノード x , y が同じグループにいるかどうかを判定する |
diff(x, y) |
ノード x , y が同じグループにいるとき、 の値を返す |
詳細は次の記事にて。
コード
上記解法の計算量は となる。構文解析が若干大変。
#include <bits/stdc++.h> using namespace std; // 重み付き Union-Find template<class Abel> struct UnionFind { const Abel UNITY_SUM = 0; // ゼロに相当する値を入れる vector<int> par; vector<Abel> diff_weight; UnionFind() { } UnionFind(int n) : par(n, -1), diff_weight(n, UNITY_SUM) {} int root(int x) { if (par[x] < 0) return x; else { int r = root(par[x]); diff_weight[x] += diff_weight[par[x]]; return par[x] = r; } } Abel calc_weight(int x) { root(x); return diff_weight[x]; } bool issame(int x, int y) { return root(x) == root(y); } bool merge(int x, int y, Abel w = 0) { w += calc_weight(x); w -= calc_weight(y); x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y), w = -w; // merge technique par[x] += par[y]; par[y] = x; diff_weight[y] = w; return true; } Abel diff(int x, int y) { return calc_weight(y) - calc_weight(x); } int size(int x) { return -par[root(x)]; } }; int main() { int N; while (cin >> N, N) { bool res = true; UnionFind<int> uf(200); // 単位個数は最悪で 200 個 map<string,int> str2id; // 単位 -> id の対応をとる int new_id = 0; // 新しい id for (int i = 0; i < N; ++i) { string ichi, unit1, equal, val, unit2; cin >> ichi >> unit1 >> equal >> val >> unit2; // 1個目の単位の番号 if (!str2id.count(unit1)) str2id[unit1] = new_id++; int id1 = str2id[unit1]; // 2個目の単位の番号 if (!str2id.count(unit2)) str2id[unit2] = new_id++; int id2 = str2id[unit2]; // 単位換算の倍率の取得 stringstream si(val.substr(3)); int diff; si >> diff; // "1 kilometre = 10^3 metre" の 3 の部分を取得 // 重み付き Union-Find 木の処理 if (uf.issame(id1, id2) && uf.diff(id1, id2) != diff) { res = false; } else { uf.merge(id1, id2, diff); } } cout << (res ? "Yes" : "No") << endl; } }
解法 (2):BFS / DFS で重みを決めて整合性を確認
次の記事の解法 (2) と同様に解ける。これが公式 editorial の解法でもある。