dinic.txt

dinic算法 相当实用

#define INF 100000000
int f[105][105],c[105][105];
int cur[105],height[105],alfl[105],queue[20000],sign[105],pre[105];
int t,s,flow;
bool bfs () {
	int l=0,r=0,u,v; 
	queue[r++]=t; 
	height[t]=0; 
	memset(b,0,sizeof(b)); 
	sign[t]=1;
	while(l<r){
		u=queue[l++];
		for(v=0;v<t;v++) if(f[v][u]<c[v][u]&&sign[v]==0) {
			height[v]=height[u]+1; 
			sign[v]=1; 
			queue[r++]=v;
		}
		if (sign[s]==1)return 1;//如果从源点出发,有边,则跳出函数,进行对边的操作.显然,这里找到了一条可行流.
	}
	return false;//没有边满足条件时,退出.
}
int maxflow() {
	int u,v,flow=0;
	memset(height,0,sizeof(height));
	while(bfs()){
		alfl[s]=INF;
		u=s;
		memset(cur,0,sizeof(cur));//每次对当前弧进行初始化.因为每次bfs()可行流流经的节点已经改变.
		while(1){
			int ok=0;
			for(v=cur[u];v<=t;v++)if(f[u][v]<c[u][v]&&height[u]==height[v]+1){
				ok=1;
				break;
			}
			if(ok==1){//如果搜索到一条边满足增广条件,进行下列操作.
				cur[u]=v+1;//记录当前的u点搜索到哪里v+1.
				pre[v]=u;//记录v点的前驱.
				alfl[v]=c[u][v]-f[u][v];//记录当前可以流经该边的流量.
				if (alfl[v]>alfl[u])alfl[v]=alfl[u];//得到允许流经该边的流量.
				u=v;//准备下一次的搜索或者准备进行流网络的修改.即将u点置成当前搜索到的点.再从u点出发,重复.
				if (v==t){
					do{//用p[u]来进行边的修改
						cur[pre[u]]=u;//记录u的前驱的搜索到的边.
							//因为dinic的搜索是从小到大逐渐++的过程,所以可以记录该点所搜索到的边来进行以后的搜索.
							//并且因为dinic每一次的ok==1就标志着有一条边会被进行判断和求最小允许流,每次的for循环只
							//对一个可行的边进行操作.所以,当for到t的时候,就该对整条路上的流量和每个点的当前弧进行更新.
							//因为u点被更新并且不确定是否u点还会有可行流,所以需要将u点加入到当前弧,为以后的搜索做准备.
						f[pre[u]][u]+=a[t];
						f[u][pre[u]]-=a[t]; 
						u=pre[u];
					}while(u!=s);
					flow+=alfl[t];//最大流加上当前可以流向t的流量.
					alfl[s]=INF;
				}
			}
			if(ok==0)
				if(u!=s){cur[u]=v;u=pre[u];}//如果没有任何边满足增广条件,并且没有搜索到源点,则让u的当前弧为v,并让u等于u的前驱.
				else break;//如果没有任何边满足增广条件，并且已经搜索到了源点，则进行下一轮的BFS()进行新一轮的层次图的构造.
		}
	}
	return flow;
}