maxflow.txt

来自「acm 常用算法和代码库」· 文本 代码 · 共 49 行

#include <iostream>
#define MAX 1000
using namespace std;
int net[MAX][MAX]={0};
int pre[MAX],que[MAX];
int n,m;
int bfs()   //寻找路径
{
	int tail,head;
	tail=head=0;
	int visited[MAX]={0};
	que[tail++]=1;

	while(head!=tail)
	{
		int now=que[head++];
		visited[now]=1;
		for(int i=1;i<=m;i++)
		{
			if(net[now][i]>0 && !visited[i])
			{
				pre[i]=now;
				que[tail++]=i;
				if(i==m) return true;
			}
		}
	}
	return false;
}
int maxflow()
{
	int res=0,i;
	while(bfs())
	{
		int min=INT_MAX;
		for(i=m;i!=1;i=pre[i])
		{
			if(min>net[pre[i]][i]) 
				min=net[pre[i]][i];  //在当前找到的路径中寻找最小流量
		}
		res+=min;
		for(i=m;i!=1;i=pre[i])
		{
			net[pre[i]][i]-=min;  //
			net[i][pre[i]]+=min;  //添加逆向边~~~
		}
	}
	return res;
}