最大流 增广路(my).txt

ACM资料大集合

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <math.h>
using namespace std;

//求网络最大流 增广路法
/*
输入：
4 5 1 4
1 2 6
1 3 5
2 3 2
2 4 5
3 4 9

输出：
11
*/
#define NMAX 12
#define NUMMAX 99
int fa[NMAX];//记录增广路,若值为正数，表示正向弧的前驱；若值为负数，表示负向弧的后继的负数
int f[NMAX][NMAX];//记录两点间流的流量
int c[NMAX][NMAX];//记录两点间流的容量
int q[NMAX];//队列

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			printf("%3d",c[i][j]);
		}
		cout<<endl;
	}
	cout<<endl;
//	system("pause");
}
void init(int num)
{	//流量、容量初始化
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			f[i][j]=-1;//容量初始为不合法
			c[i][j]=0;//流量初始为0
		}
	}
}

int get_maxliu(int start,int end,int num)
{	//num为点的总数，start为源点，end为汇点
	int qs,qe,s,e,now,min,sum,j,i;
	s=start;
	sum=0;
	do
	{
		for(i=0;i<=num;i++)
		{
			fa[i]=q[i]=0;
		}
//		memset(fa,0,sizeof(fa));//增广路初始化
		fa[start]=-1;//增广路上，源点的后继是负数
		qs=0;qe=1;
		//	memset(q,0,sizeof(q));//队列初始化
		q[qe]=start;//开始，队列的队头是源点
		//以下是一遍地查找增广路
		while(qs<qe&&fa[end]==0)
		{	//print(num);
			now=q[++qs];//从队列中取出要找到后继的节点
			for(j=1;j<=num;j++)
			{
				//将所有能合法做now节点后继都保存到队列里
				//故在A，B处无break();否则只会保存第一个节点后继
				if(fa[j]==0)//没有被标记
				{
					if(f[now][j]<c[now][j])
					{	//前向弧
						fa[j]=now;
						q[++qe]=j;//A处，合法后继入队
					}
					else if(f[j][now]>0)
					{   //后向弧
						fa[j]=-now;
						q[++qe]=j;//B处，合法后继入队
					}
				}
			}
		}
		if(fa[end]!=0)//存在源点到汇点的增广路
		{
			e=end;//从汇点起，开始求该次增流的大小
			min=99999999;
			while(e!=start)
			{
				now=fa[e];//取出增广路的相对前驱
				if(now>0)	//前向弧
				{	
					if(min>c[now][e]-f[now][e])
						min=c[now][e]-f[now][e];
				}
				else		//后向弧
				{
					if(min>f[e][-now])
						min=f[e][-now];
				}
				e=abs(fa[e]);
			}
			sum+=min;//总增流
			e=end;//从汇点起，进行该次的增流
			while(e!=start)
			{	//改进流
				now=fa[e];
				if(now>0)	f[now][e]+=min;//前向弧
				else f[e][-now]-=min;//后向弧
				e=abs(fa[e]);
			}
		}
	}while(fa[end]!=0);//每次查找增广路时，只要能求出汇点的前继，循环继续
//	cout<<"sum="<<sum<<endl;
	return sum;
} 

int main()
{
	int num,pnum,i,ta,tb,tc,start,end;
	scanf("%d%d%d%d",&num,&pnum,&start,&end);
	init(num);
	for(i=0;i<pnum;i++) 
	{
		scanf("%d%d%d",&ta,&tb,&tc);
		c[ta][tb]=tc;
	}
	cout<<get_maxliu(start,end,num)<<endl;
	return 0;
}