Summary
有N種水果，現知道許多以下的關系：
aX<=bY
表示：a個X水果的重量小于b個水果Y的重量。給出許多這些小于關系后，最后問a個X水果和b個Y水果的重量關系。水果的數目不超過一百。
Solution
這個問題可以轉化成圖論問題考慮。視每個水果為一個節點，對于關系aX<=bY，我們可以建立一條從Y到X的邊，權值為a/b，意思是Y水果的單位重量至少是X水果的a/b倍。
然后使用floyd算法求一次最短路，將加法改成乘法即可。算出每種水果之間的重量比例關系。
檢查算出來的矩陣，如果有g[i][i]>1，那么就是出現矛盾，判為INCONSISTENT。
如果要判定aX是否<=bY，也就是判定Y>=(a/b)X。對于算出的矩陣，g[Y][X]表示Y>=g[Y][X]X。若判定Y>=(a/b)X成立，必有(a/b)<=G[Y][X]。
對于相等的情況特判一下即可。
1
#include <cstdio>
2#include <cstring>
3#include <string>
4#include <map>
5#include <algorithm>
6using namespace std;
7#define N 105
8#define EPS 1e-8
9double g[N][N];
10char s1[N], s2[N];
11int n;
12map<string, int> MAP;
13
14
void solve() 
{
15
int i, j, k, cnt = 0, a, b, x, y;
16 memset(g, 0, sizeof(g));
17 MAP.clear();
18
for (i = 0; i < n; i++) {
19 scanf("%d%s%d%s", &a, s1, &b, s2);
20 if (MAP.find(string(s1)) == MAP.end()) MAP[string(s1)] = cnt++;
21 if (MAP.find(string(s2)) == MAP.end()) MAP[string(s2)] = cnt++;
22 x = MAP[string(s1)], y = MAP[string(s2)];
23 g[y][x] = max(g[y][x], (double) a / b);
24
}
25
26 for (i = 0; i < cnt; i++)
27 g[i][i] = 1;
28 for (k = 0; k < cnt; k++)
29 for (i = 0; i < cnt; i++)
30 for (j = 0; j < cnt; j++)
31 if (g[i][k] > 0 && g[k][j] > 0) g[i][j] = max(g[i][j], g[i][k] * g[k][j]);
32
33 scanf("%d%s%d%s", &a, s1, &b, s2);
34 x = MAP[string(s1)], y = MAP[string(s2)];
35
36 for (i = 0; i < cnt; i++)
37 if (g[i][i] > 1) {
38 puts("INCONSISTENT");
39 return;
40 }
41 if (g[y][x] >= (double) a / b - EPS && g[x][y] >= (double) b / a - EPS) puts("==");
42 else if (g[y][x] >= (double) a / b - EPS) puts("<=");
43 else if (g[x][y] >= (double) b / a - EPS) puts(">=");
44 else puts("UNAVAILABLE");
45
46
}
47int main() {
48 while (scanf("%d", &n) && n)
49 solve();
50 return 0;
51}
52