poj 1273 最大流(Ford-Fulkerson算法和Dinic算法分别实现)

最大流模板题目

Ford-Fulkerson：

#include <stdio.h>
#include <string.h>
#define N 202
int q[N];//用于找增广路径的队列
int c[N][N],f[N][N];//c是路径的容量，f保存寻找过程中的流量
int a[N],p[N];//p存放一条增广路径的前一个结点
int n,m;
int maxflow(int s,int t){//从s到t的最大流
	int i,j,res = 0;
	int front,rear;
	while(1){
		front = rear = -1;
		q[++rear] = s;
		memset(a,0,sizeof(a));
		memset(p,0,sizeof(p));
		a[s] = 0x3fffffff;
		while(front < rear){
			i = q[++front];
			for(j = 1;j<=n;j++)
				if(!a[j] && c[i][j]-f[i][j]>0){
					a[j] = a[i]<c[i][j]-f[i][j]?a[i]:c[i][j]-f[i][j];
					q[++rear] = j;
					p[j] = i;
				}
		}
		if(!a[t])
			break;
		for(j = t;j!=s;j=p[j]){
			f[p[j]][j] += a[t];
			f[j][p[j]] -= a[t];
		}
		res += a[t];
	}
	return res;
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%d %d",&m,&n)!=EOF){
		int i,x,y,w;
		memset(c,0,sizeof(c));
		memset(f,0,sizeof(f));
		for(i = 0;i<m;i++){
			scanf("%d %d %d",&x,&y,&w);
			c[x][y] += w;
		}
		printf("%d\n",maxflow(1,n));
	}
	return 0;
}

当残余网络的分层操作无法算出汇点的层次（即BFS到达不了汇点）时，算法结束，最大流求出。一般用栈实现DFS，这样就能从栈中提取出增广路径。

#include <stdio.h>
#include <string.h>
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define N 205
int n,m;
int flow[N][N],visited[N],layer[N],q[N],stack[N];
int do_layer(int s,int t){//用队列对节点进行分层
	int i,front,rear,now;
	front = rear = -1;
	memset(layer,-1,sizeof(layer));
	q[++rear] = s;
	layer[s] = 0;
	while(front < rear){
		now = q[++front];
		for(i = s;i<=t;i++)
			if(layer[i]==-1 && flow[now][i]>0){
				layer[i] = layer[now]+1;
				if(i == t)
					return 1;
				q[++rear] = i;
			}
	}
	return 0;
}
int dinic(int s,int t){//用堆栈模拟dfs
	int i,now,top=-1,aug,res=0,temp,vs,vt;
	while(do_layer(s,t)){
		memset(visited,0,sizeof(visited));
		stack[++top] = s;
		visited[s] = 1;
		while(top>-1){
			now = stack[top];
			if(now == t){
				aug = INF;temp = 0;//temp保存回溯的位置
				for(i = 1;i<=top;i++){//找本次增广的流量
					vs = stack[i-1];
					vt = stack[i];
					if(aug>flow[vs][vt] && flow[vs][vt]>0){
						aug = min(aug,flow[vs][vt]);
						temp = vs;
					}
				}
				res += aug;
				for(i = 1;i<=top;i++){//更新流量以及反向边
					vs = stack[i-1];
					vt = stack[i];
					flow[vs][vt] -= aug;
					flow[vt][vs] += aug;
				}
				while(stack[top]!=temp){
					visited[stack[top]] = 0;
					top--;
				}
			}else{
				for(i = s;i<=t;i++)
					if(!visited[i] && flow[now][i]>0 && layer[i]==layer[now]+1){
						stack[++top] = i;
						visited[i] = 1;
						break;
					}
				if(i > t)
					top--;
			}
		}
	}
	return res;
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%d %d",&m,&n)!=EOF){
		int i,a,b,w;;
		memset(flow,0,sizeof(flow));
		for(i = 0;i<m;i++){
			scanf("%d %d %d",&a,&b,&w);
			flow[a][b] += w;
		}
		printf("%d\n",dinic(1,n));
	}
	return 0;
}