• <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>

            poj1860 Currency Exchange: spfa / Bellman Ford

            1) 實質就是是確定圖中是否存在正環--沿著這個環一直走能夠使環內節點的權值無限增長.
            2) 特點是: 每個邊的權值是動態變化的, 這點提醒我們適合用Bellman Ford算法來處理(SPFA實質上是Bellman Ford的優化, 算法思想是一樣的).

            SPFA算法:
             1#include <cstdio>
             2#include <queue>
             3using namespace std;
             4
             5#define EXPNTNUM (100 + 10)
             6#define CURNUM (100 + 10)
             7
             8struct Node {
             9    int to;
            10    Node* next;
            11    double commission, ratio;
            12}
            ;
            13
            14Node nodeHead[CURNUM + 1];
            15Node edge[EXPNTNUM * 2 + 2];
            16int pos = 0;
            17Node* getEdge() {
            18    return edge + pos++;
            19}

            20
            21double maxWeight[CURNUM + 1];
            22
            23void addEdge(int from, int to, double ratio, double commission) {
            24    Node* e = getEdge();
            25    Node* n = nodeHead + from;
            26    e->to = to;
            27    e->ratio = ratio;
            28    e->commission = commission;
            29    e->next = n->next;
            30    n->next = e;
            31}

            32
            33int main() {
            34    int currencyNum, pointNum, currencyNumHas;
            35    int i, j, a, b;
            36    double ratioab, ratioba, comab, comba;
            37    double currencisHas;
            38
            39    scanf("%d%d%d%lf"&currencyNum, &pointNum, &currencyNumHas, &currencisHas);
            40    for (i = 1; i <= currencyNum; ++i) {
            41        maxWeight[i] = 0;
            42        nodeHead[i].next = NULL;
            43    }

            44    for (i = j = 0; i < pointNum; ++i) {
            45        scanf("%d%d"&a, &b);
            46        scanf("%lf%lf%lf%lf"&ratioab, &comab, &ratioba, &comba);
            47        addEdge(a, b, ratioab, comab);
            48        addEdge(b, a, ratioba, comba);
            49    }

            50
            51    maxWeight[currencyNumHas] = currencisHas;
            52
            53    queue<int> q;
            54    q.push(currencyNumHas);
            55    int maxEdgeCount = 0;
            56    while (true{
            57        int u = q.front();
            58        q.pop();
            59        for (Node* tra = nodeHead[u].next; tra != NULL; tra = tra->next) {
            60            double temp = (maxWeight[u] - tra->commission) * 
            61                tra->ratio;
            62            if (maxWeight[tra->to] < temp) {
            63                maxWeight[tra->to] = temp;
            64                q.push(tra->to);
            65            }

            66        }

            67        maxEdgeCount++;
            68        if (maxWeight[currencyNumHas] > currencisHas) {
            69            printf("YES\n");
            70            break;
            71        }

            72        if (q.empty()) {
            73            printf("NO\n");
            74            break;
            75        }

            76    }

            77
            78
            79    return 0;
            80}

            81


            Bellman Ford算法:

             1#include <cstdio>
             2using namespace std;
             3
             4#define EXPNTNUM (100 + 10)
             5#define CURNUM (100 + 10)
             6
             7struct Edge {
             8    int from, to;
             9    double commission, ratio;
            10}
            ;
            11
            12Edge edge[EXPNTNUM * 2 + 2];
            13
            14double maxWeight[CURNUM + 1];
            15
            16void setEdge(Edge &e, int from, int to, double ratio, double commission) {
            17    e.from = from;
            18    e.to = to;
            19    e.ratio = ratio;
            20    e.commission = commission;
            21}

            22
            23int main() {
            24    int currencyNum, pointNum, currencyNumHas;
            25    int i, j, a, b;
            26    double ratioab, ratioba, comab, comba;
            27    double currencisHas;
            28
            29    scanf("%d%d%d%lf"&currencyNum, &pointNum, &currencyNumHas, &currencisHas);
            30    for (i = j = 0; i < pointNum; ++i) {
            31        scanf("%d%d"&a, &b);
            32        scanf("%lf%lf%lf%lf"&ratioab, &comab, &ratioba, &comba);
            33        setEdge(edge[j++], a, b, ratioab, comab);
            34        setEdge(edge[j++], b, a, ratioba, comba);
            35    }

            36
            37    int edgeCount = j;
            38    for (i = 1; i <= currencyNum; ++i) {
            39        maxWeight[i] = 0;
            40    }

            41    maxWeight[currencyNumHas] = currencisHas;
            42
            43    int maxEdgeCount = 0;
            44    bool improved;
            45    while (true{
            46        improved = false;
            47        for (i = 0; i < edgeCount; ++i) {
            48            if (maxWeight[edge[i].from] <= 0{
            49                continue;
            50            }

            51            double temp = (maxWeight[edge[i].from] - edge[i].commission) * 
            52                edge[i].ratio;
            53            if (maxWeight[edge[i].to] < temp) {
            54                maxWeight[edge[i].to] = temp;
            55                improved = true;
            56            }

            57        }

            58        maxEdgeCount++;
            59        if (maxWeight[currencyNumHas] > currencisHas) {
            60            printf("YES\n");
            61            break;
            62        }

            63        if (!improved) {
            64            printf("NO\n");
            65            break;
            66        }

                          // 1) 在提交時不要這個也不會很慢
                          // 2) 下面代碼的意思是: 在已經插入了currencyNum(節點數)個邊的前提下, 
                          // 如果圖中不存在正回路(這個正回路會使回路內的節點權值無限增加, 
                          // 從而能夠通過兌換貨幣的形式賺錢), 
                          // 則再插入邊不會使任意一個節點的權值增加. 反過來, 
                          // 如果已經插入了currencyNum條邊, 還能插入邊使節點權值增加, 
                          // 則圖中存在正回路.
                          // 3) 這個終止條件可以使外層while循環至多在currencyNum次后結束. 
                          // 以避免回路權值增長很慢導致循環很多次的極端情況.
            67        if (maxEdgeCount > currencyNum && improved) {
            68            printf("YES\n");
            69            break;
            70        }

            71    }

            72
            73    return 0;
            74}

            75
            76


            posted on 2011-07-04 09:18 cucumber 閱讀(338) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            午夜精品久久久久9999高清| 精品无码久久久久久久动漫| 狠狠色综合网站久久久久久久高清| 久久综合五月丁香久久激情| 欧美国产成人久久精品| 97精品依人久久久大香线蕉97| 国产精品久久久久jk制服| 亚洲国产二区三区久久| 中文字幕无码久久人妻| 久久99精品国产自在现线小黄鸭| 久久播电影网| 久久Av无码精品人妻系列| 久久久久亚洲AV无码专区桃色| 日日噜噜夜夜狠狠久久丁香五月| 中文字幕久久欲求不满| 亚洲国产精品无码久久SM| 久久无码精品一区二区三区| 少妇久久久久久久久久| 久久久国产视频| 国产亚洲色婷婷久久99精品91| 亚洲国产一成人久久精品| 亚洲AV伊人久久青青草原| 久久精品九九亚洲精品天堂| 亚洲AV日韩精品久久久久久 | 久久99国产精品99久久| 一本色道久久HEZYO无码| 无码人妻久久一区二区三区蜜桃| 99久久国产综合精品五月天喷水| 国产精品久久久久影视不卡| 久久综合噜噜激激的五月天| 久久精品国产男包| 伊人久久大香线蕉成人| 久久久久亚洲av成人无码电影| 国产999精品久久久久久| 久久96国产精品久久久| 精品综合久久久久久97超人| 久久av无码专区亚洲av桃花岛| 欧美黑人激情性久久| 久久久无码精品亚洲日韩按摩| 亚洲国产精品成人久久| 久久w5ww成w人免费|