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

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>
            精品电影一区| 欧美xx69| 久久久久久9999| 欧美日韩国产麻豆| 国产农村妇女精品一二区| 亚洲国产视频一区| 欧美在线高清| 日韩视频在线免费| 久久亚洲一区二区三区四区| 国产精品你懂的在线欣赏| 亚洲激情小视频| 亚洲精品欧美| 亚洲黄色毛片| 亚洲国产精品福利| 久久久久九九九| 91久久精品日日躁夜夜躁欧美| 欧美伊人久久大香线蕉综合69| 欧美中文在线字幕| 国产精品视频一| 亚洲午夜未删减在线观看| 亚洲国产综合91精品麻豆| 欧美日韩天堂| 野花国产精品入口| 欧美激情一区二区三区不卡| 久久综合电影一区| 在线播放日韩欧美| 久久久夜色精品亚洲| 性久久久久久| 国产一区二区三区在线观看网站 | 亚洲综合色噜噜狠狠| 欧美日韩免费在线视频| 久久精品人人做人人爽| 久久福利精品| 影音先锋中文字幕一区二区| 亚洲片在线资源| 国产伊人精品| 欧美成人精品一区| 欧美fxxxxxx另类| 亚洲精品视频一区| 亚洲精品小视频| 国内成人在线| 正在播放亚洲一区| 国产亚洲精品7777| 亚洲美女黄网| 91久久久在线| 久久精品在线观看| 亚洲精品久久久久久下一站| 午夜欧美大片免费观看| 亚洲一级在线观看| 欧美激情欧美狂野欧美精品| 亚洲永久在线观看| 久久se精品一区二区| 亚洲一区二区视频在线| 欧美成人精品在线播放| 蜜臀久久久99精品久久久久久 | 一区二区高清在线| 国产欧美精品久久| 在线亚洲免费视频| 亚洲视频在线观看视频| 午夜精品在线观看| 亚洲欧美日韩精品久久久| 久久理论片午夜琪琪电影网| 欧美一区二区三区在线播放| 国产精品久久久久久久久久免费看 | 欧美高清不卡| 亚洲主播在线播放| 欧美日韩成人综合| 亚洲乱码国产乱码精品精天堂| 亚洲精品一区二区三区婷婷月| 免费欧美电影| 亚洲人成网站在线播| 日韩亚洲欧美中文三级| 欧美一级大片在线免费观看| 亚洲精品美女久久久久| 欧美承认网站| 99精品欧美一区| 一区二区三区中文在线观看| 久久久91精品国产一区二区精品| 久久久久久国产精品mv| 国产精品swag| 91久久精品久久国产性色也91| 国产亚洲女人久久久久毛片| 久久精品国产v日韩v亚洲| 猛干欧美女孩| 一区二区欧美日韩| 蜜桃精品一区二区三区| 久久精品国产久精国产一老狼| 国模大胆一区二区三区| 欧美成人tv| 一本色道久久综合精品竹菊| 久久精品国产v日韩v亚洲 | 欧美午夜视频在线观看| 性色一区二区三区| 欧美激情国产日韩精品一区18| 艳妇臀荡乳欲伦亚洲一区| 国产精品久久久久久久免费软件| 欧美自拍丝袜亚洲| 亚洲高清不卡一区| 亚洲大胆视频| 久久久久久一区| 亚洲日本中文字幕| 久久成人精品| 国产视频一区免费看| 亚洲一区视频| 香蕉久久夜色精品国产使用方法| 欧美香蕉视频| 久久久综合香蕉尹人综合网| 9色porny自拍视频一区二区| 理论片一区二区在线| 在线成人激情黄色| 国产精品成人免费精品自在线观看| 性欧美大战久久久久久久久| 亚洲国产一区二区三区青草影视| 欧美在线影院在线视频| 一区二区三区精密机械公司| 一区二区三区无毛| 国产精品亚洲精品| 欧美精品123区| 久久免费高清视频| 欧美中文在线免费| 欧美理论电影在线播放| 亚洲激情视频| 樱桃国产成人精品视频| 亚洲尤物精选| 欧美激情区在线播放| 久久国产精彩视频| 亚洲欧美日韩国产精品| 99热在这里有精品免费| 亚洲国产精品久久91精品| 狂野欧美激情性xxxx| 欧美一区二区在线观看| 亚洲综合色网站| 亚洲视频网站在线观看| 夜夜嗨一区二区三区| 亚洲日本理论电影| 亚洲福利精品| 亚洲国产色一区| 欧美国产日本在线| 欧美成人精品影院| 蜜臀91精品一区二区三区| 鲁大师成人一区二区三区| 久久久久综合| 久久久另类综合| 久久久久一本一区二区青青蜜月| 久久成人这里只有精品| 久久高清一区| 久久人人爽人人爽| 免费不卡中文字幕视频| 欧美不卡一卡二卡免费版| 欧美99在线视频观看| 欧美韩日一区二区| 最新国产成人在线观看| 99精品99| 亚洲欧美视频| 亚洲美女黄色片| 99re热精品| 亚洲色图在线视频| 香港久久久电影| 久久久噜噜噜| 欧美成人国产一区二区| 欧美日韩一区二区视频在线观看| 国产精品九九| 国产一区二区激情| 亚洲激情网站| 午夜国产一区| 一本久道久久综合中文字幕| 亚洲欧美日韩成人高清在线一区| 新狼窝色av性久久久久久| 久久久亚洲高清| 亚洲国产精品尤物yw在线观看| 一本色道久久综合狠狠躁篇怎么玩| 亚洲午夜一区二区三区| 亚洲视频电影在线| 欧美自拍偷拍| 欧美美女日韩| 国产一区二区三区成人欧美日韩在线观看 | 一本久久综合亚洲鲁鲁五月天 | 老司机午夜精品视频在线观看| 欧美黄色一区二区| 亚洲亚洲精品三区日韩精品在线视频| 欧美诱惑福利视频| 欧美精品尤物在线| 国产性天天综合网| 一区二区三区视频在线观看| 欧美专区在线播放| 亚洲精品乱码久久久久久| 欧美一激情一区二区三区| 欧美激情视频一区二区三区在线播放| 国产精品一区二区三区四区| 国产农村妇女毛片精品久久麻豆| 在线日韩欧美| 欧美亚洲日本国产| 亚洲日韩欧美视频一区| 久久精品国产96久久久香蕉| 欧美体内谢she精2性欧美| 国产精品a久久久久| 91久久在线| 玖玖视频精品| 亚洲欧美日韩精品久久| 欧美午夜久久|