max_flow.cpp

图论的一些常用代码

//求网络最大流,用邻接阵形式
//参数:节点数n,矩阵mat[][],源点source,汇点sink,每条边的流量 flow[][]
//返回:最大流 每条边的流量flow
#define MAX 100
#define inf 100000000
int ford_fulkerson(int n,int mat[][MAX],int source,int sink,int flow[][MAX])
{
	int pre[MAX],que[MAX],d[MAX],p,q,t,i,j;		//d[]用来表示还能容纳的容量

	//源点和汇点相同则返回
    if (source==sink)
		return inf;

	//初始化每条边的流量
	for (i=0;i<n;i++)
		for (j=0;j<n;flow[i][j++]=0);

	//反复标记,反复查找增益路径
	while(1)
	{
		//pre用来标记父结点
		for (i=0;i<n;pre[i++]=0);

		pre[t=source]=source+1,d[t]=inf;

		//广度探索 que是用数组模拟的队列
		for (p=q=0;p<=q && !pre[sink];t=que[p++])
		{
			for (i=0;i<n;i++)
			{
				//正向边
				if (!pre[i] && (j=mat[t][i]-flow[t][i]))
					pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;

				//反向边
				else if (!pre[i] && (j=flow[i][t]))
					pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
			}
		}

		//结束
		if (!pre[sink]) break;

		//从汇点开始增加边的流量,直到源点
		for (i=sink;i!=source;)
		{
			if (pre[i]>0)
				flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
			else
				flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
		}
	}

	//把和源点相接的边的流量相加即最大流量
	for (j=i=0;i<n;j+=flow[source][i++]);
	return j;
}