• <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 閱讀(299) 評論(0)  編輯 收藏 引用 所屬分類: F_圖算法

            導航

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

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久无码精品一区二区三区| 人妻丰满AV无码久久不卡| 九九久久99综合一区二区| 国产精品美女久久久久网| 久久久久久综合一区中文字幕| 国产成人综合久久精品尤物| 久久综合视频网站| 久久se精品一区精品二区| 久久精品国产亚洲av瑜伽| 性高湖久久久久久久久| 99re这里只有精品热久久 | 久久久久一区二区三区| 亚洲国产成人久久一区久久 | 91精品国产91热久久久久福利| 国产精品免费久久久久久久久| 18禁黄久久久AAA片| 国产精品美女久久久久av爽| 久久人人妻人人爽人人爽| 武侠古典久久婷婷狼人伊人| 国产综合精品久久亚洲| 国产激情久久久久影院小草| 久久99国内精品自在现线| 久久久久免费看成人影片| 一本久久a久久精品亚洲| 少妇内射兰兰久久| 九九久久自然熟的香蕉图片| 性欧美大战久久久久久久久| 亚洲精品乱码久久久久久久久久久久 | 久久久久AV综合网成人| 91精品国产乱码久久久久久| 国内精品久久久久伊人av| 夜夜亚洲天天久久| 亚洲欧美成人久久综合中文网| 久久久久久久久波多野高潮| 国产精品美女久久久久| 久久精品免费大片国产大片 | 狠狠狠色丁香婷婷综合久久俺| 久久免费视频观看| 综合网日日天干夜夜久久| 婷婷久久综合九色综合98| 久久久久亚洲AV无码观看|