青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

A Za, A Za, Fighting...

堅信:勤能補拙

PKU 1273 Drainage Ditches

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

思路:
第一道最大流,Edmonds-Karp算法
參考了別人的代碼,其實自己也能寫出來,不過肯定沒有這么精致(*^__^*) 嘻嘻……
從別人的代碼里學到很多,例如:
一條路徑只需要pre[]數組進行保存即可,路徑的殘留容量也可以邊擴展(BFS)邊記錄,還有代碼居然就只需要一個殘留網絡的二維數組

代碼:
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define MAX_M 201
 5 #define INF 0x7FFFFFFF
 6 #define Min(a,b) ((a)<(b) ? (a) : (b))
 7 int n, m, source, sink;
 8 int pre[MAX_M]; /* excellent for path recording */
 9 int flow[MAX_M];
10 int residual[MAX_M][MAX_M]; /* only need this matrix */
11 int queue[MAX_M];
12 
13 int
14 bfs() /* operation on the residual network */
15 {
16     int i, head, tail, cur;
17     head = -1;
18     tail = 0;
19     memset(pre, -1sizeof(pre));
20     for(i=1; i<=m; i++)
21         flow[i] = INF;
22     queue[tail] = source;
23     pre[source] = 0;
24     while(head < tail) {
25         ++head;
26         cur = queue[head];
27         if(cur == sink)
28             return flow[sink];
29         for(i=1; i<=m; i++) {
30             if(pre[i]!=-1 || !residual[cur][i])
31                 continue;
32             pre[i] = cur;
33             flow[i] = Min(flow[cur], residual[cur][i]);
34             ++tail;
35             queue[tail] = i;
36         }
37     }
38     return -1;
39 }
40 
41 int
42 edmonds_karp()
43 {
44     int tmp, next, cur, rt = 0;
45     while(1) {
46         tmp = bfs();
47         if(tmp == -1/* there's no argment path */
48             return rt;
49         rt += tmp;
50         cur = sink;
51         while(cur != source) {
52             next = cur;
53             cur = pre[cur];
54             residual[cur][next] -= tmp;
55             residual[next][cur] += tmp;
56         }
57     }
58 }
59 
60 int
61 main(int argc, char **argv)
62 {
63     int i, f, t, c, ans;
64     while(scanf("%d %d"&n, &m) != EOF) {
65         memset(residual, 0sizeof(residual));
66         for(i=1; i<=n; i++) {
67             scanf("%d %d %d"&f, &t, &c);
68             residual[f][t] += c; /* Attention: multiple lines */
69         }
70         source = 1;
71         sink = m;
72         ans = edmonds_karp();
73         printf("%d\n", ans);
74     }
75 }

posted on 2010-09-16 21:10 simplyzhao 閱讀(206) 評論(0)  編輯 收藏 引用 所屬分類: F_圖算法

導航

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

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久久久久欧美| 亚洲六月丁香色婷婷综合久久| 一区二区三区国产精品| 欧美高清在线一区二区| 久久综合久久久| 亚洲精品国产日韩| 亚洲精品影院在线观看| 国产精品爱啪在线线免费观看| 小处雏高清一区二区三区| 午夜在线不卡| 精品成人乱色一区二区| 欧美激情一区二区三区在线视频观看 | 久久精品女人| 亚洲国产va精品久久久不卡综合| 欧美成人精品一区| 欧美日韩成人综合| 亚洲欧美日韩人成在线播放| 久久成人精品| 99国产精品| 香蕉成人啪国产精品视频综合网| 在线成人中文字幕| 亚洲天堂第二页| 亚洲第一成人在线| 亚洲一区二区毛片| 亚洲人成亚洲人成在线观看图片| 亚洲一区二区三区色| 亚洲精品久久久久久久久久久久| 一本色道久久综合亚洲精品小说| 红桃av永久久久| 一区二区三区免费看| 在线日韩av片| 亚洲视频在线一区| 99re亚洲国产精品| 欧美亚洲一区三区| 亚洲国产裸拍裸体视频在线观看乱了中文 | 欧美激情2020午夜免费观看| 久久一本综合频道| 亚洲欧洲日本国产| 久久国产精品一区二区| 亚洲欧美国产va在线影院| 亚洲在线观看免费| 欧美在线地址| 午夜视频在线观看一区| 亚洲女性裸体视频| 伊人久久久大香线蕉综合直播| 亚洲电影免费观看高清| 国产精品国产精品| 久久久久免费视频| 久久综合999| 一区二区三区欧美亚洲| 亚洲欧美日韩天堂| 一区二区在线观看视频在线观看 | 国产婷婷成人久久av免费高清| 久久国产手机看片| 欧美不卡视频| 久久亚洲一区二区| 欧美紧缚bdsm在线视频| 老司机免费视频久久| 国产精品欧美精品| 欧美福利在线观看| 国产精品羞羞答答| 亚洲精品免费网站| 国内精品嫩模av私拍在线观看| 久久香蕉国产线看观看网| 亚洲一级电影| 国产模特精品视频久久久久| 亚洲在线日韩| 亚洲国产日韩美| 亚洲欧美另类久久久精品2019| 国产日韩精品视频一区二区三区 | 国产婷婷色一区二区三区四区 | 最新亚洲激情| 久久久91精品| 亚洲专区在线| 欧美成人精品一区| 亚洲精品日韩久久| 午夜国产欧美理论在线播放| 国产日韩欧美高清免费| 久久深夜福利| 今天的高清视频免费播放成人 | 欧美日本亚洲视频| 免费中文日韩| 在线电影国产精品| 久久国产一区二区| 久久久久久久精| 国产精品久久久久久久午夜片| 91久久精品日日躁夜夜躁欧美 | 国内精品久久久久久久影视蜜臀| 亚洲综合首页| 欧美性猛交xxxx乱大交退制版| 欧美高清在线播放| 亚洲韩国精品一区| 免费不卡在线视频| 韩国一区二区在线观看| 亚洲精品视频在线播放| 亚洲国产精品999| 久久久久久九九九九| 在线免费不卡视频| 免费观看亚洲视频大全| 欧美电影电视剧在线观看| 在线观看欧美日韩| 久久久久久精| 久久躁狠狠躁夜夜爽| 亚洲第一二三四五区| 老司机aⅴ在线精品导航| 久久精品亚洲精品国产欧美kt∨| 蜜桃久久av一区| 久久久久9999亚洲精品| 精品成人久久| 欧美精品v国产精品v日韩精品 | 狠狠入ady亚洲精品| 欧美一区二区高清在线观看| 久久这里只有| 亚洲精品在线一区二区| 蜜乳av另类精品一区二区| 欧美成人在线免费观看| 在线一区亚洲| 国产欧美日韩三区| 免费亚洲网站| 亚洲男女自偷自拍图片另类| 久久久久久网站| av不卡在线| 国产一区二区中文字幕免费看| 久久免费黄色| 一区二区av在线| 亚洲人体偷拍| 欧美精品1区2区3区| 亚洲午夜在线观看| 欧美激情一区二区三区蜜桃视频 | 欧美一区二区三区免费视频| 久久久久国产免费免费| 一个人看的www久久| 国产乱码精品| 欧美精品三级| 久久精品国产精品亚洲精品| 亚洲精品国产视频| 久久久www成人免费毛片麻豆| 国产欧美精品日韩精品| 亚洲欧美激情一区| 欧美国产在线电影| 午夜一区二区三视频在线观看 | 久久精品国产v日韩v亚洲| 亚洲区一区二| 久久字幕精品一区| 欧美亚洲午夜视频在线观看| 99re6热只有精品免费观看| 国产在线不卡视频| 国产精品白丝av嫩草影院| 欧美黑人国产人伦爽爽爽| 亚洲国产视频直播| 欧美在线一二三四区| 国产一区清纯| 欧美日韩国产综合视频在线观看中文| 欧美亚洲在线| 亚洲午夜激情在线| 亚洲人成在线影院| 亚洲国产精品综合| 久久婷婷久久一区二区三区| 亚洲一区二区免费| 一本久久综合| 一区二区三欧美| 国产精品成人观看视频国产奇米| 亚洲精品免费一区二区三区| 亚洲一区二区三区乱码aⅴ蜜桃女| 亚洲国产成人精品久久久国产成人一区| 久久精品首页| 久久午夜精品一区二区| 久久精品视频网| 久久久视频精品| 久久精品一本久久99精品| 亚洲欧美日韩一区| 亚洲欧美一区二区原创| 亚洲视频999| 在线视频欧美精品| 久久精品国产清自在天天线| 久久久999| 免费一区视频| 性亚洲最疯狂xxxx高清| 久久精品国产精品| 久久精品国产亚洲a| 美女精品在线| 最新国产成人av网站网址麻豆| 欧美一区精品| 欧美一区二区三区四区在线| 欧美激情精品久久久久久免费印度 | 亚洲视频免费观看| 亚洲一区二区三区精品在线| 欧美一区=区| 久久久一区二区三区| 另类激情亚洲| 久久综合九色九九| 免费观看久久久4p| 欧美久久久久久| 国产精品久久久久久久久免费樱桃 | 国产欧美日韩在线观看| 狠狠88综合久久久久综合网| 一区在线播放视频| 亚洲性感美女99在线| 久久免费视频观看| 久久9热精品视频|