AOJ 2207 無矛盾な単位系 (UTPC 2010 D)

これも重み付き Union-Find で解ける問題！

• 問題へのリンク
• editorial

問題概要

具体例として一つの入力ケースを示す。

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 が同じグループにいるとき、 の値を返す

詳細は次の記事にて。

qiita.com

コード

上記解法の計算量は となる。構文解析が若干大変。

#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 の解法でもある。

drken1215.hatenablog.com