1 条题解
-
0
#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
- 上传者