PKU 3860 Fruit Weights 图论 SPFA最短路变形

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<stringint> MAP;
13 
14void solve() {
15    int i, j, k, cnt = 0, a, b, x, y;
16    memset(g, 0sizeof(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

posted on 2010-10-14 17:42 yzhw 阅读(145) 评论(0)  编辑 收藏 引用 所属分类: graph


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜