dinic(数组)

  一直想学dinic算法，但是没找到好的资料，看了《网络流》感觉这书太好了，感觉加深了对网络流的理解，先学了SAP算法，然后就是Dinic算法。 其实2者差不多。

Dinic算法的实质是在层次图里找最短增广路进行增广， 通过BFS构造层次图，然后采用SAP的算法，但是有3点改进：

1.we do not change the distance label of node i, but subsequently tern node i is blocked, A blocked node has no admissible path to the sink node.

2.：we define an arc (i,j) to be admissible if d[i] = d[j] + 1 r[i][j]> 0 and j is not blocked.

3.When the source node is blocked, by performing a BFS we recompute the distance labels of all nodes exactly.

其他就和SAP一样就行了。

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAX = 225;
const int oo = 2100000000;
int n,m,c[MAX][MAX],remain[MAX][MAX],source,sink,nc,np //remain为剩余图，又名残留网络
int dis[MAX],block[MAX];
void bfs() //bfs建立层次图,即用数组dis[]记录各个结点的深度
{
int q[MAX],head=0,tail=0,u,v;
for(int i=0;i<=sink;i++)
dis[i]=oo;
q[++head]=sink;
dis[sink]=0;
while(tail < head)
{
u = q[++tail]; //出队
for(v=0;v<=sink;v++)
if(dis[v] ==oo && remain[v][u]>0)
{
dis[v]=dis[u]+1;
q[++head]=v;
}
}
}
//dfs搜索增益路径,dinic == dfs
int dinic()
{
bfs(); //之后source在最后一层
int top = source,pre[MAX],flow=0; //top是最短增广路最前面一个节点,pre保存路径,同时作为dfs堆栈
int i,j,k,low[MAX];
memset(low,0,sizeof(low));
memset(block,0,sizeof(block));
//下为dfs标准过程
while(dis[source]!=oo) //dinic算法结束条件：从源点到汇点没有路,终点sink为第0层
{
bool flag = false;
low[source]=oo;
for(i=0;i<=sink;i++) //在top的邻接边中找容许边
if(remain[top][i]>0 && dis[top]==dis[i]+1 && !block[i])
{
flag = true;
break;
}
if(flag) //如果找到
{
low[i] = remain[top][i]; //low 保存当前节点的最小容量,且终点sink的最小容量为路径流量
if(low[i] > low[top])
low[i]=low[top]; //更新
pre[i] = top;top=i;


if(top == sink) //找到路
{
flow += low[sink];
j = top;
while(j != source) //回溯更新(剩余图)残留网络remain[max][max]
{
k = pre[j];
remain[k][j]-=low[sink];
remain[j][k]+=low[sink];
j = k;
}
top = source; //准备下一循环,重新找增广路
memset(low,0,sizeof(low));
}


}
else //无容许边存在，则阻塞当前点
{
block[top] = 1;
if(top != source)
top = pre[top]; //非源点阻塞就回溯,继续dfs
else //如果源点阻塞了就重新建立层次图
{
bfs();
memset(block,0,sizeof(block));
}
}
}
return flow;
}
main()
{

}