简介

算法介绍(层次图 算法流程 时间复杂度)

代码实现(递归实现 非递归实现 PASCAL代码实现)

简介

网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n^2*m) 。

算法介绍

层次图

层次图，就是把原图中的点按照到到源的距离分“层”，只保留不同层之间的边的图。

算法流程

1、根据残量网络计算层次图。

2、在层次图中使用DFS进行增广直到不存在增广路。

3、重复以上步骤直到无法增广。

时间复杂度

因为在Dinic的执行过程中，每次重新分层，汇点所在的层次是严格递增的，而n个点的层次图最多有n层，所以最多重新分层n次。在同一个层次图中，因为每条增广路都有一个瓶颈，而两次增广的瓶颈不可能相同，所以增广路最多m条。搜索每一条增广路时，前进和回溯都最多n次，所以这两者造成的时间复杂度是O(nm)；而沿着同一条边(i,j)不可能枚举两次，因为第一次枚举时要么这条边的容量已经用尽，要么点j到汇不存在通路从而可将其从这一层次图中删除。综上所述，Dinic算法时间复杂度的理论上界是O(n^2*m)。

代码实现

递归实现

代码简短，效率略低。（不是dinic，是最短路径增值）

bool build()//建立层次图

{

int x,y;

memset(d,-1,sizeof(d));

memset(G,-1,sizeof(G));

bg=ed=d[s]=0;Q[ed++]=s;G[s]=g[s];

while(bg<ed)

{

x=Q[bg++];

for(int i=g[x];i+1;i=np)

{

y=to;

if(cap&&d[y]==-1)

{

d[y]=d[x]+1;G[y]=g[y];

if(y==t)return true;

Q[ed++]=y;

}

}

}

return false;

}

int find(int x,int low=inf)//进行增广

{

if(x==t)return low;

int ret=0,y;

for(int &i=G[x];i+1;i=np)//注意i是引用

{

y=to;

if(cap && d[y]==d[x]+1 && (ret=find(y,low<?cap)))

{

cap-=ret;cap[vp]+=ret;

return ret;

}

}

return 0;

}

int dinic()//主过程

{

int flow,ret=0;

while(build())

while(flow=find(s))

ret+=flow;

return ret;

}

非递归实现

效率更高，但代码量略有些大。

//Author: dd_engi

void Dinic()

{

for(;;){

BFS();

if(D[T]==-1)break;

int path_n=0;

int x=S;

memcpy(cur,E,sizeof(cur));

for(;;){

if(x==T){

int mink=-1,delta=INT_MAX;

for(int i=0;i<path_n;++i){

if(path[i]->c<delta){

delta=path[i]->c;

mink=i;

}

}

for(int i=0;i<path_n;++i){

path[i]->c-=delta;

path[i]->back->c+=delta;

}

path_n=mink;

x=path[path_n]->x;

}

edge* e;

for(e=cur[x];e;e=e->next){

if(e->c==0)

continue;

int y=e->y;

if(D[x]+1==D[y])

break;

}

cur[x]=e;

if(e){

path[path_n++]=e;

x=e->y;

}

else{

if(path_n==0)

break;

D[x]=-1;

--path_n;

x=path[path_n]->x;

}

}

}

}

PASCAL代码实现

program dinic;

type

lx=array[1..1000] of longint;

var

lu:lx;

a,b:array[0..1000,0..1000] of longint;

d:array[1..1000] of longint;

v:array[1..1000] of boolean;

dist:array[1..1000] of longint;

head,tail:longint;

t:array[1..1000] of boolean;

sum,ans,x,y,s,i,p,j,k,m,n:longint;

q,c:boolean;

procedure spfa(s:longint);

var

i,j,now,sum:longint;

begin

fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false);

for j:=1 to n do dist[j]:=maxlongint; dist[s]:=0; v[s]:=true; d[1]:=s; head:=1; tail:=1;

while head<=tail do

begin

now:=d[head];

for i:=1 to b[now,0] do

if dist[b[now,i]]>dist[now]+1

then

begin

dist[b[now,i]]:=dist[now]+1;

if not v[b[now,i]] then begin inc(tail); d[tail]:=b[now,i]; v[b[now,i]]:=true; end;

end;

v[now]:=false; inc(head);

end;

end;

procedure dfs(x,d:longint);

var

i:longint;

begin

lu[d]:=x; t[x]:=true; if x=n then begin c:=false;s:=d;end;

for i:=1 to n do if (a[x,i]>0)and c and (not t[i])and (dist[x]<=dist[i]) then dfs(i,d+1);

end;

procedure expand(l:lx;len:longint);

var

i,j,k:longint;

begin

k:=maxlongint; for i:=1 to len do if k>l[i] then k:=l[i]; sum:=k;

for i:=2 to len do begin dec(a[l[i-1],l[i]],k); inc(a[l[i],l[i-1]],k); end;

end;

begin

read(n,m);

for i:=1 to m do

begin

read(x,y,k); a[x,y]:=k;

inc(b[x,0]); b[x,b[x,0]]:=y;

end;

c:=false;

while true do

begin

spfa(1); for i:=1 to n do t[i]:=false;

k:=maxlongint; c:=true; dfs(1,1);

if c then break; expand(lu,s); inc(ans,sum);

end;

writeln(ans);

end.