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>
6
using namespace std;
7
#define N 105
8
#define EPS 1e-8
9
double g[N][N];
10
char s1[N], s2[N];
11
int n;
12
map<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
}
47
int main()
{
48
while (scanf("%d", &n) && n)
49
solve();
50
return 0;
51
}
52