最大流 增广路(xd).txt

ACM资料大集合

#include <stdio.h>
#include <math.h>
#include <memory.h>

int n, np, nc, m, s, t;
int fa[104], q[104], f[104][104], c[104][104];
// 用fa记录增广路，q是求增广路中所需要用的队列，f,c是采用邻接矩阵的方式来记录网络中的流量和容量

void proc()
{
	int qs, qt, d, d0, i, j, ans = 0;

	fa[t] = 1;

	while (fa[t] != 0)
	{
		qs = 0; qt = 1;						//队列的首尾指针初始化
		q[qt] = s;
		memset(fa, 0, sizeof(fa));			//增广路径初始化
		fa[s] = s;
		while (qs < qt && fa[t] == 0)		//若没有找到到汇点的增广路或还可以继续寻找增广路
		{
			i = q[++qs];
			for (j = 1; j <= t; j++)
				if (fa[j] == 0)				//点j没有标记过
					if (f[i][j] < c[i][j])	//(i,j)的流量小于容量：存在一条(i,j)的前向弧
					{
						fa[j] = i;
						q[++qt] = j;
					}
					else
						if (f[j][i] > 0)	//(j,i)的流量大于0，存在一条(j,i)的后向弧
						{
							fa[j] = -i;
							q[++qt] = j;
						}
		}
		if (fa[t] != 0)						//如果找到一条从源点到汇点的增广路就改进当前流
		{
			d0 = 10000000;
			i = t;
			while (i != s)					//寻找最大的可改进量
			{
				if (fa[i] > 0)
				{
					if ((d = c[fa[i]][i] - f[fa[i]][i]) < d0)
						d0 = d;
				}
				else
					if (f[i][-fa[i]] < d0)
						d0 = f[i][-fa[i]];
				i = abs(fa[i]);
			}
			ans += d0;						//总流量累加
			i = t;
			while (i != s)					//改进流
			{
				if (fa[i] > 0)
					f[fa[i]][i] += d0;
				else
					f[i][-fa[i]] -= d0;
				i = abs(fa[i]);
			}
		}
	}
	printf("%d\n", ans);					//输出最大流
}

void main()
{
	int i, u, v, cc;
	while (scanf("%d%d%d%d", &n, &np, &nc, &m) == 4)
	{
		s = n + 2; t = n + 1;				//以下是构图
		memset(f, 0, sizeof(f));
		memset(c, 0, sizeof(c));
		for (i = 1; i <= m; i++)			//对于原图中边(u,v)连一条容量为cc的弧
		{
			while (getchar() != '(');
			scanf("%d,%d)%d", &u, &v, &cc);
			c[u + 1][v + 1] = cc;
		}
		for (i = 1; i <= np; i++)			//对于PowerStation从源点连一条容量为cc的弧
		{
			while (getchar() != '(');
			scanf("%d)%d", &u, &cc);
			c[s][u + 1] = cc;
		}
		for (i = 1; i <= nc; i++)			//对于Consumer连一条容量为cc的弧到汇点
		{
			while (getchar() != '(');
			scanf("%d)%d", &u, &cc);
			c[u + 1][t] = cc;
		}

		proc();								//求最大流
	}
}