呵呵,又從DK那偷代碼了,好興奮哈,以下是這個算法的簡單介紹,不過我用它去解決HDU的1532 竟然TLE,郁悶.到時候再繼續(xù)問問DK吧...so 煩躁.
哈哈 終于經過大牛的指點 原來本算法是從0開始標號的......
Dinic是個很神奇的網絡流算法。它是一個基于“層次圖”的時間效率優(yōu)先的最大流算法。
層次圖是什么東西呢？層次，其實就是從源點走到那個點的最短路徑長度。于是乎，我們得到一個定理：從源點開始，在層次圖中沿著邊不管怎么走，經過的路徑一定是終點在剩余圖中的最短路。（摘自WC2007王欣上論文）注意，這里是要按照層次走。
那么，MPLA（最短路徑增值）的一大堆復雜的證明我就略掉了，有興趣的請自行參閱WC2007王欣上神牛的論文。
首先我們得知道，Dinic的基本算法步驟是，先算出剩余圖，然后用剩余圖算層次圖，然后在層次圖里找增廣路。不知道你想到沒有，這個層次圖找增廣路的方法，恰恰就是Ford-Fulkerson類算法的時間耗費最大的地方，就是找一個最短的增廣路。所以呢，層次圖就相當于是一個已經預處理好的增廣路標志圖。
如何實現Dinic呢？
首先我們必然要判一下有沒有能到達終點的路徑（判存在增廣路與否），在這個過程中我們順便就把層次圖給算出來了（當然不用算完），然后就沿著層次圖一層一層地找增廣路；找到一條就進行增廣（注意在沿著層次圖找增廣路的時候使用棧的結構，把路徑壓進棧）；增廣完了繼續(xù)找，找不到退棧，然后繼續(xù)找有沒有與這個結點相連的下一層結點，直到棧空。如果用遞歸實現，這個東西就很好辦了，不過我下面提供的程序是用了模擬棧，當然這樣就不存在結點數過多爆棧的問題了……不過寫起來也麻煩了一些，對于“繼續(xù)找”這個過程我專門開了一個數組存當前搜索的指針。
上面拉拉雜雜說了一大堆，實際上在我的理解中，層次圖就是一個流從高往低走的過程（這玩意兒有點像預流推進的標號法……我覺得），在一條從高往低的路徑中，自然有些地方會有分叉；這就是Dinic模擬棧中退棧的精華。這就把BFS的多次搜索給省略了不說，時間效率比所謂的理論復雜度要高得多。
這里有必要說到一點，網絡流的時間復雜度都是很悲觀的，一般情況下絕對沒有可能到達那個復雜度的。
#include<iostream>
using namespace std;
const long maxn=300;
const long maxm=300000;
const long inf=0x7fffffff;
struct node
{
long v,next;
long val;
}s[maxm*2];
long level[maxn],p[maxn],que[maxn],out[maxn],ind;
void init()
{
ind=0;
memset(p,-1,sizeof(p));
}
inline void insert(long x,long y,long z)
{
s[ind].v=y;
s[ind].val=z;
s[ind].next=p[x];
p[x]=ind++;
s[ind].v=x;
s[ind].val=0;
s[ind].next=p[y];
p[y]=ind++;
}
inline void insert2(long x,long y,long z)
{
s[ind].v=y;
s[ind].val=z;
s[ind].next=p[x];
p[x]=ind++;
s[ind].v=x;
s[ind].val=z;
s[ind].next=p[y];
p[y]=ind++;
}
long max_flow(long n,long source,long sink)
{
long ret=0;
long h=0,r=0;
while(1)
{
long i;
for(i=0;i<n;++i)
level[i]=0;
h=0,r=0;
level[source]=1;
que[0]=source;
while(h<=r)
{
long t=que[h++];
for(i=p[t];i!=-1;i=s[i].next)
{
if(s[i].val&&level[s[i].v]==0)
{
level[s[i].v]=level[t]+1;
que[++r]=s[i].v;
}
}
}
if(level[sink]==0)break;
for(i=0;i<n;++i)out[i]=p[i];
long q=-1;
while(1)
{
if(q<0)
{
long cur=out[source];
for(;cur!=-1;cur=s[cur].next)
{
if(s[cur].val&&out[s[cur].v]!=-1&&level[s[cur].v]==2)
{
break;
}
}
if(cur>=0)
{
que[++q]=cur;
out[source]=s[cur].next;
}
else
{
break;
}
}
long u=s[que[q]].v;
if(u==sink)
{
long dd=inf;
long index=-1;
for(i=0;i<=q;i++)
{
if(dd>s[que[i]].val)
{
dd=s[que[i]].val;
index=i;
}
}
ret+=dd;
//cout<<ret<<endl;
for(i=0;i<=q;i++)
{
s[que[i]].val-=dd;
s[que[i]^1].val+=dd;
}
for(i=0;i<=q;i++)
{
if(s[que[i]].val==0)
{
q=index-1;
break;
}
}
}
else
{
long cur=out[u];
for(;cur!=-1;cur=s[cur].next)
{
if(s[cur].val&&out[s[cur].v]!=-1&&level[u]+1==level[s[cur].v])
{
break;
}
}
if(cur!=-1)
{
que[++q]=cur;
out[u]=s[cur].next;
}
else
{
out[u]=-1;
q--;
}
}
}
}
return ret;
}
long m,n;
int main()
{
while(scanf("%ld %ld",&m,&n)!=EOF)
{
init();
for(int i=0;i<n;i++)
{
long from,to,cost;
scanf("%ld %ld %ld",&from,&to,&cost);
insert(--from,--to,cost);
}
long Start,End;
scanf("%ld %ld",&Start,&End);
printf("%ld\n",max_flow(n,--Start,--End));
}
return 0;
}