并查集加上分?jǐn)?shù)運(yùn)算就可以了。
兩種物品之間的兌換比率可以用分?jǐn)?shù)來表示，兩種物品之間是否存在聯(lián)系用并查集來表示。
#include <stdio.h>
#include <string.h>
typedef struct {
int a, b;
} frac ;
#define MAX_ITEM 64
char item[MAX_ITEM][32];
int item_cnt;
struct {
frac f;
int p;
} set[MAX_ITEM];
int gcd(int a, int b)
{
int t;
if (a > b) {
a ^= b;
b ^= a;
a ^= b;
}
while (a) {
t = a;
a = b % a;
b = t;
}
return b;
}
frac init(int a, int b)
{
frac r;
int g = gcd(a, b);
r.a = a / g;
r.b = b / g;
return r;
}
frac mul(frac a, frac b)
{
return init(a.a * b.a, a.b * b.b);
}
frac div(frac a, frac b)
{
return init(a.a * b.b, a.b * b.a);
}
int find(int i)
{
int p;
if (set[i].p == i)
return i;
p = find(set[i].p);
set[i].f = mul(set[set[i].p].f, set[i].f);
set[i].p = p;
return p;
}
int insert(char *s)
{
int i;
for (i = 0; i < item_cnt; i++)
if (!strcmp(s, item[i]))
return i;
strcpy(item[item_cnt], s);
return item_cnt++;
}
int main()
{
char op[16], sa[32], sb[32];
int a, b, ia, ib, i, p;
frac f;
for (i = 0; i < MAX_ITEM; i++) {
set[i].p = i;
set[i].f = init(1, 1);
}
while (scanf("%s", op), op[0] != '.') {
if (op[0] == '!') {
scanf("%d%s%*s%d%s", &a, sa, &b, sb);
ia = insert(sa);
ib = insert(sb);
find(ia);
p = set[ia].p;
set[p].p = ib;
set[p].f = div(init(b, a), set[ia].f);
} else {
scanf("%s%*s%s", sa, sb);
ia = insert(sa);
ib = insert(sb);
find(ia);
find(ib);
if (set[ia].p == set[ib].p) {
f = div(set[ia].f, set[ib].f);
printf("%d %s = %d %s\n", f.b, item[ia], f.a, item[ib]);
} else
printf("? %s = ? %s\n", item[ia], item[ib]);
}
}
return 0;
}