Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 2207 - Consistet Unit System

問題文 : 無矛盾な単位系


解法 :

重み付きunion-find 木を使います.
普通のunion-find の機能を拡張する形で実装します.

$[unit_1] = k [unit_2]$ というクエリが来たとき, この2 つが同じ集合にあれば
$[unit_1] = A [unit_0],\ [unit_2] = B [unit_0]$ となるある単位$[unit_0]$ が存在するので,
$[unit_1] / [unit_2] = A / B = k$ が成り立つはずです. この基準となる単位系は通常のunion-find の実装と同じように求めることができます.
新しく併合する時は, $[unit_1]$ を$[unit_2]$ の親となるノードで表すので, $[unit_1] = k [unit_2] = k * B * [unit_0]$ となるように併合します. ここで, $[unit_1]$ は別の集合に属していたものなので, 親によって$A * [unit_0']$ と表されたことを思いだし, $[unit_0'] = k * B / A * [unit_0]$ として整合性がとれるように併合する事を忘れないようにしないといけません.


今, 係数はすべて10 のべきなので掛け算や割り算を使わずに引き算, 足し算で表現することが可能です.

コード :

#include <cstdio>
#include <map>
#include <string>
 
using namespace std;
 
pair<int, int> par[256];
 
void init(int n)
{
    for (int i = 0; i < n; i++){
        par[i] = make_pair(i, 0);
    }
}
 
pair<int, int> find(int x)
{
    if (par[x].first == x) return (par[x]);
    pair<int, int> ret = find(par[x].first);
    return (par[x] = make_pair(ret.first, par[x].second + ret.second));
}
 
bool same(int u, int v)
{
    return (find(u).first == find(v).first);
}
 
void merge(int u, int v, int val)
{
    pair<int, int> uu = find(u);
    pair<int, int> vv = find(v);
     
    if (uu.first == vv.first) return;

    par[uu.first] = make_pair(vv.first, vv.second + val - uu.second);
}
 
int main()
{
    int n;
     
    while (scanf("%d", &n) && n){
        getchar();
         
        map<string, int> mp;
        init(256);
        bool ok = true;
         
        for (int i = 0; i < n; i++){
            char s[1024], t[1024];
            int val;
             
            scanf("1 %s = 10^%d %s", s, &val, t);
            getchar();
             
            string ss = s, st = t;
            if (!mp.count(ss)){
                int ct = mp.size();
                mp[ss] = ct;
            }
            if (!mp.count(st)){
                int ct = mp.size();
                mp[st] = ct;
            }
             
            int u = mp[ss], v = mp[st];
            if (same(u, v)){
                if (par[u].second - par[v].second != val) ok = false;
            }
            else {
                merge(u, v, val);
            }
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
     
    return (0);
}