• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(149) 評論(0)  編輯 收藏 引用 所屬分類: graph

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

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            99久久久精品| 狠狠色丁香婷婷久久综合| 久久青青草原精品国产| 国产一级持黄大片99久久| 91亚洲国产成人久久精品| 四虎亚洲国产成人久久精品| 无码精品久久久天天影视| 91久久精品国产成人久久| 日韩欧美亚洲综合久久| 久久99精品国产99久久| 亚洲午夜无码久久久久小说| 久久97精品久久久久久久不卡| 久久免费99精品国产自在现线| 久久精品九九亚洲精品| 色欲综合久久躁天天躁| 久久99国产精品99久久| 波多野结衣久久一区二区| 国产精品欧美久久久久天天影视| 久久国产亚洲精品| 久久精品亚洲男人的天堂| 精品午夜久久福利大片| 久久久国产乱子伦精品作者| 久久精品免费全国观看国产| 久久本道久久综合伊人| 国产91久久精品一区二区| 性欧美大战久久久久久久久 | 狠狠色丁香婷婷综合久久来来去| 人妻无码精品久久亚瑟影视| 欧美日韩成人精品久久久免费看| AA级片免费看视频久久| 久久99国产精品二区不卡| 国产91色综合久久免费分享| 久久99精品久久久久久久不卡| 99久久无色码中文字幕人妻| 精品久久久中文字幕人妻| 热久久最新网站获取| 久久综合久久综合亚洲| 99久久香蕉国产线看观香| 老男人久久青草av高清| 亚洲狠狠婷婷综合久久久久| 日韩人妻无码精品久久久不卡|