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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 3259 Wormholes

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=3259

            思路:
            這題的描述挺有意思,通過某些路徑可以回到過去之類,其實就是求是否存在負權回路的問題
            Bellman-Ford算法的典型應用
            一個問題是,Bellman-Ford用于判斷從某個源點可達的負權回路,而這里求的是整個圖,而且也沒有說明該圖一定是connected的
            解決上述問題的一個方法就是添加一個頂點,然后從該新頂點到每個其他頂點添加一條權值為0的邊

            代碼:
             1 /* Bellman-Ford algorithm */
             2 #include<stdio.h>
             3 #include<stdlib.h>
             4 #include<string.h>
             5 #define MAX_N 501
             6 #define MAX_M 2501
             7 #define MAX_W 201
             8 #define INF 0x7FFFFFFF
             9 struct Edge {
            10     int from, to;
            11     int cost;
            12 } edges[MAX_M*2+MAX_W+MAX_N];
            13 int d[MAX_N];
            14 int n, total;
            15 
            16 void
            17 init()
            18 {
            19     int i, m, w, f, t, c;
            20     scanf("%d %d %d"&n, &m, &w);
            21     total = 0/* the number of edges */
            22     for(i=0; i<m; i++) {
            23         scanf("%d %d %d"&f, &t, &c);
            24         edges[total].from = f;
            25         edges[total].to = t;
            26         edges[total++].cost = c;
            27         edges[total].from = t;
            28         edges[total].to = f;
            29         edges[total++].cost = c;
            30     }
            31     for(i=0; i<w; i++) {
            32         scanf("%d %d %d"&f, &t, &c);
            33         edges[total].from = f;
            34         edges[total].to = t;
            35         edges[total++].cost = c*(-1);
            36     }
            37     /* in order to keep connectivity, add one vertex: '0' */
            38     for(i=1; i<=n; i++) {
            39         edges[total].from = 0;
            40         edges[total].to = i;
            41         edges[total++].cost = 0;
            42     }
            43 }
            44 
            45 void
            46 relax(struct Edge *e)
            47 {
            48     if(d[e->from] == INF)
            49         return;
            50     if(d[e->to] > d[e->from]+e->cost)
            51         d[e->to] = d[e->from]+e->cost;
            52 }
            53 
            54 int
            55 bellman_ford()
            56 {
            57     int i, j;
            58     for(i=0; i<=n; i++)
            59         d[i] = INF;
            60     d[0= 0;
            61     for(i=0; i<n; i++)  /* n+1 vertices */
            62         for(j=0; j<total; j++)  /* 2*m+w+n edges */
            63             relax(edges+j);
            64     for(j=0; j<total; j++) {
            65         if(d[edges[j].to] > d[edges[j].from]+edges[j].cost)
            66             return 0;
            67     }
            68     return 1;
            69 }
            70 
            71 int
            72 main(int argc, char **argv)
            73 {
            74     int F;
            75     scanf("%d"&F);
            76     while(F--) {
            77         init();
            78         printf("%s\n", bellman_ford()==1?"NO":"YES");
            79     }
            80 }

            posted on 2010-09-07 22:29 simplyzhao 閱讀(301) 評論(0)  編輯 收藏 引用 所屬分類: F_圖算法

            導航

            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产小视频精品久久久三级| 伊人久久大香线蕉综合网站| 久久99精品久久久久久久不卡 | 久久99国产精一区二区三区| 久久亚洲精品视频| 怡红院日本一道日本久久 | 精品国产婷婷久久久| 久久综合久久伊人| 久久国产色AV免费观看| 国产精品久久久天天影视香蕉| 合区精品久久久中文字幕一区| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 久久久噜噜噜www成人网| 国产精品亚洲美女久久久| 综合网日日天干夜夜久久| 18岁日韩内射颜射午夜久久成人| 久久人与动人物a级毛片| 国产一久久香蕉国产线看观看| 一本一道久久a久久精品综合 | 精品国产福利久久久| 久久天天躁狠狠躁夜夜2020一| 久久精品国产精品亚洲| 97久久国产亚洲精品超碰热| 东方aⅴ免费观看久久av| 亚洲国产香蕉人人爽成AV片久久| 一级做a爰片久久毛片16| 91精品国产综合久久久久久| 一本色道久久88—综合亚洲精品 | 久久大香香蕉国产| 亚洲中文字幕无码一久久区| 久久人人青草97香蕉| 久久影视国产亚洲| 日韩影院久久| 欧美伊人久久大香线蕉综合| 2019久久久高清456| 日日狠狠久久偷偷色综合0| 久久久久亚洲av成人无码电影| 久久久久国产| 国产精品久久久久久五月尺| 97久久国产露脸精品国产| 无码国内精品久久人妻|