網絡流之最大流問題

Reference：

http://blog.csdn.net/rrerre/article/details/6751520

http://blog.csdn.net/y990041769/article/details/21026445

http://www.nocow.cn/index.php/Translate:USACO/NetworkFlow

?

最大流Edmonds_Karp算法模板：

EK算法即增廣路算法。

最大流最小割定理：最大流等于最小割

見白書P210

?

算法思想：

step 1. 令所有弧的流量為0，從而構造一個流量為0的可行流f（稱作零流）。
step 2. 若f中找不到可改進路則轉step 5；否則找到任意一條可改進路P。
step 3. 根據P求delta。
step 4. 以delta為改進量，更新可行流f。轉step 2。
step 5. 算法結束。此時的f即為最大流。

算法的關鍵步驟是step 2，即：判斷是否存在可改進路，若存在又如何求。
可以考慮用廣度優先搜索。設置標志數組，記錄頂點是不是被訪問過；使用隊列來存儲已經訪問過的頂點；另用一個一維數組p[i]，記錄每個頂點是由哪個頂點擴展而來（即記錄父親節點）。
首先S入隊列。然后每次取隊首頂點v，分析所有與v相鄰的未訪問頂點u：
1、存在弧<v, u>（正向弧），且u未訪問。若f(v,u)<C(v,u)（非飽和弧），那么u入隊列，給u打上“已訪問”的標志，記u的父親節點為v。
2、存在弧<u, v>（反向弧），且u未訪問。若f(u,v) > 0（非零流弧），那么u入隊列，給u打上“已訪問”的標志，記u的父親節點為-v。（以示和正向弧的區別）。
擴展完成后，若T還沒有被訪問就必然不存在可改進路；否則就從T出發，根據記錄好的每個頂點的父親節點信息，順藤摸瓜，找出可改進路（同時還可以計算出delta）。

?

起點st，終點m

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n,m,st,en;
int cap[300][300];    //cap[u][v]:邊(u,v)上的最大流量
int flow[300][300];    //flow[u][v]:邊(u,v)上當前的流量
int a[300];        //a[u]:訪問標記，同時還記錄下delta值
int p[300];        //記錄父節點用
const int inf=100000000;int EK()            //st-->m
{queue<int> Q;memset(flow,0,sizeof(flow));memset(p,-1,sizeof(p));int f=0,minflow=inf;while(1){memset(a,0,sizeof(a));a[st]=inf;          Q.push(st);         while(!Q.empty()){int u=Q.front();Q.pop();for(int v=1;v<=m;v++)if(!a[v]&&cap[u][v]>flow[u][v]){p[v]=u;Q.push(v);a[v]=a[u]<cap[u][v]-flow[u][v]?a[u]:cap[u][v]-flow[u][v];}}if(a[m]==0) break;for (int u=m;u!=st;u=p[u])          {flow[p[u]][u]+=a[m];flow[u][p[u]]-=a[m];}f+=a[m];}return f;
}int main()
{int S,E,C;while (cin>>n>>st>>m)       //st->m
    {memset(cap,0,sizeof(cap));for (int i=1;i<=n;i++){cin>>S>>E>>C;cap[S][E]+=C;　　　　//處理重邊。有些題目，一條路上先給了容量30，然后重復了一次50，這時候這條路上的容量應該是30+50。
        }cout<<EK()<<endl;}return 0;
}

?

模板例題：

hdu1532

?

補充：需要拆點的問題：POJ3281

http://www.2cto.com/kf/201210/164289.html

http://moxi466839201.blog.163.com/blog/static/18003841620112316351118/

?

-------------------------------------------------------------------------------------------

補充個ISAP模板，比EK算法快，但是難想難寫。看不懂T^T...

#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
typedef  struct {int v,next,val;} edge;
const int MAXN=20010;
const int MAXM=500010;
edge e[MAXM];
int p[MAXN],eid;
void init(){memset(p,-1,sizeof(p));eid=0;}
void insert1(int from,int to,int val) //有向
{e[eid].v=to;e[eid].val=val;e[eid].next=p[from];p[from]=eid++;swap(from,to);e[eid].v=to;e[eid].val=0;e[eid].next=p[from];p[from]=eid++;
}
void insert2(int from,int to,int val) //無向
{e[eid].v=to;e[eid].val=val;e[eid].next=p[from];p[from]=eid++;swap(from,to);e[eid].v=to;e[eid].val=val;e[eid].next=p[from];p[from]=eid++;
}
int n,m;//n為點數 m為邊數
int h[MAXN];
int gap[MAXN];
int s,t;
int dfs(int pos,int cost)
{if (pos==t) return cost;int j,minh=n-1,lv=cost,d;for (j=p[pos];j!=-1;j=e[j].next){int v=e[j].v,val=e[j].val;if(val>0){if (h[v]+1==h[pos]){if (lv<e[j].val) d=lv;else d=e[j].val;d=dfs(v,d);e[j].val-=d;e[j^1].val+=d;lv-=d;if (h[s]>=n) return cost-lv;if (lv==0) break;}if (h[v]<minh)    minh=h[v];}}if (lv==cost){--gap[h[pos]];if (gap[h[pos]]==0) h[s]=n;h[pos]=minh+1;++gap[h[pos]];}return cost-lv;
}
int isap(int st,int ed)
{s=st;t=ed;int ret=0;memset(gap,0,sizeof(gap));memset(h,0,sizeof(h));gap[st]=n;while (h[st]<n)ret+=dfs(st,INT_MAX);return ret;
}
int main()
{while(cin>>m>>n){init();for(int i=0;i<m;i++){int u,v,c;scanf("%d%d%d",&u,&v,&c);insert1(u,v,c);}printf("%d\n",isap(1,n));}return 0;
}

?

補充：sap、isap(sap+gap優化)、dinic算法：

http://blog.csdn.net/sprintfwater/article/details/7913181

sap算法：

http://www.cnblogs.com/longdouhzt/archive/2011/09/04/2166187.html