1 条题解

  • 0
    @ 2025-5-5 12:17:28
    #include <iostream>
    #include <map>
    #include <string>
    #include <stdio.h>
    using namespace std;
    
    const int MAX = 100;
    
    int parent[MAX];
    int numer[MAX]; // A[i] / B[i] = rate between i and parent[i]
    int denom[MAX];
    int count = 0;
    map<string, int> name2id;
    
    int gcd(int a, int b) {
        while (b) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
    
    void add_item(const string &s) {
        if (name2id.count(s)) return;
        name2id[s] = count;
        parent[count] = count;
        numer[count] = 1;
        denom[count] = 1;
        count++;
    }
    
    int find(int x) {
        if (parent[x] != x) {
            int orig_parent = parent[x];
            parent[x] = find(parent[x]);
            numer[x] = numer[x] * numer[orig_parent];
            denom[x] = denom[x] * denom[orig_parent];
            int g = gcd(numer[x], denom[x]);
            numer[x] /= g;
            denom[x] /= g;
        }
        return parent[x];
    }
    
    void unite(int a, int b, int na, int nb) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;
    
        // a * na = b * nb
        // a/ra = numer[a]/denom[a], b/rb = numer[b]/denom[b]
        // so: na * numer[a]/denom[a] = nb * numer[b]/denom[b]
        int left = na * numer[a] * denom[b];
        int right = nb * numer[b] * denom[a];
    
        parent[ra] = rb;
        numer[ra] = right;
        denom[ra] = left;
        int g = gcd(numer[ra], denom[ra]);
        numer[ra] /= g;
        denom[ra] /= g;
    }
    
    int main() {
        string line;
        while (getline(cin, line)) {
            if (line[0] == '.') break;
    
            if (line[0] == '!') {
                int m, n;
                char a[21], b[21];
                sscanf(line.c_str(), "! %d %s = %d %s", &m, a, &n, b);
                add_item(a);
                add_item(b);
                unite(name2id[a], name2id[b], m, n);
            } else if (line[0] == '?') {
                char a[21], b[21];
                sscanf(line.c_str(), "? %s = %s", a, b);
                if (!name2id.count(a) || !name2id.count(b)) {
                    cout << "? " << a << " = ? " << b << endl;
                    continue;
                }
                int ida = name2id[a];
                int idb = name2id[b];
                int ra = find(ida);
                int rb = find(idb);
                if (ra != rb) {
                    cout << "? " << a << " = ? " << b << endl;
                } else {
                    int left = numer[ida] * denom[idb];
                    int right = numer[idb] * denom[ida];
                    int g = gcd(left, right);
                    left /= g;
                    right /= g;
                    cout << right << " " << a << " = " << left << " " << b << endl;
                }
            }
        }
        return 0;
    }
    
    
    
    • 1

    信息

    ID
    571
    时间
    1000ms
    内存
    10MiB
    难度
    5
    标签
    递交数
    4
    已通过
    1
    上传者