題目鏈接

第一道最大流，赤裸裸的模版題，剛好可以熟悉模版用。今天看了一下最大流，就看了一個EK算法，感覺有點(diǎn)和二分圖匹配算法有點(diǎn)相似，對于最大流問題有點(diǎn)了解了，不過為什么這么做，也不是 很懂，只是把代碼給敲了一遍，以后慢慢學(xué)習(xí)。

EK算法，過程是先BFS找到str到end的一條路，然后每條路上的流量（key[][]記錄）取這些路中流量的最小值（flow[]記錄），在這條路上的流量都減去這個值，然后建立反向邊，然后繼續(xù)找增廣路，直到找不到為止。有前驅(qū)的結(jié)點(diǎn)不會再找了，所以幾遍之后肯定找不到了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <cmath>
 5 #include <queue>
 6 using namespace std;
 7 #define INF 0x7fffffff
 8 int key[101][101];
 9 int path[101],flow[101],n,m,str,end;
10 queue<int>que;
11 int bfs()
12 {
13     int i,t;
14     while(!que.empty()) que.pop();
15     memset(path,-1,sizeof(path));
16     path[str] = 0;
17     flow[str] = INF;//初始化
18     que.push(str);
19     while(!que.empty())//BFS
20     {
21         t = que.front();
22         que.pop();
23         if(t == end) break;//已經(jīng)找到end了
24         for(i = 1;i <= n;i ++)
25         {
26             if(i != str&&key[t][i]&&path[i] == -1)
27             {
28                 flow[i] = flow[t] < key[t][i] ? flow[t]:key[t][i];//記錄流量
29                 que.push(i);
30                 path[i] = t;//記錄前驅(qū)
31             }
32         }
33     }
34     if(path[end] == -1)//找不到路徑時
35     return -1;
36     else
37     return flow[end];
38 }
39 int EK()
40 {
41     int ans = 0,pre,now,step;
42     while((step = bfs()) != -1)
43     {
44         ans += step;
45         now = end;
46         while(now != str)
47         {
48             pre = path[now];
49             key[now][pre] += step;
50             key[pre][now] -= step;
51             now = pre;
52         }
53     }
54     return ans;
55 }
56 int main()
57 {
58     int i,t,sv,ev,w,num = 0;
59     scanf("%d",&t);
60     while(t--)
61     {
62         num ++;
63         memset(key,0,sizeof(key));
64         scanf("%d%d",&n,&m);
65         for(i = 1;i <= m;i ++)
66         {
67             scanf("%d%d%d",&sv,&ev,&w);
68             key[sv][ev] += w;
69         }
70         str = 1;end = n;
71         printf("Case %d: %d\n",num,EK());
72     }
73     return 0;
74 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/naix-x/archive/2012/11/20/2779611.html

總結(jié)

以上是生活随笔為你收集整理的HDU 3549 Flow Problem(最大流模版EK算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。