poj 1459（最大流）

2019-04-13 21:09发布生成海报

站内文章 / 模拟电子

10915 0

题意：在一个电路系统中有发电厂，有用电者，有变电站，发电厂只能生产电不能用电，用电者只能用电不能生产电，变电站只能传输电。思路：这是一道很明显的最大流。建立一个超级源点0，从0到各个发电站建立一条容量为发电站产电数额的边，以保证每个发电站供出的电小于或等于自己的产电数额；建立一个超级汇点n+1，从各个用电者到n+1建一条容量为用电者最多用电数额的边；然后对题中给定的m个triplets建边。最后从0到n+1求最大流。参考代码：

#include <iostream>
#include <cstdio>

using namespace std;

int G[120][120],n;
int c[120][120],f[120][120],que[120],pre[120];
bool vis[120];

int ek(int s,int t)
{
	int i,j,k,flow=0;
	memset(f,0,sizeof(f));
	while(true)
	{
		memset(vis,0,sizeof(vis));
		int head=0,tail=0;
		que[tail++]=s;
		vis[s]=true;
		while(head<tail)
		{
			k=que[head++];
			if(k==t)
			{
				break;
			}
			for(i=0;i<=n+1;i++)
			{
				if(c[k][i]>0&&!vis[i])
				{
					que[tail++]=i;
					vis[i]=true;
					pre[i]=k;
				}
			}
		}
		if(k!=t)
		{
			break;
		}
		int min1=1<<30;
		j=t;
		i=pre[j];
		while(j!=s)
		{
			if(c[i][j]<min1)
			{
				min1=c[i][j];
			}
			j=i;
			i=pre[j];
		}
		flow+=min1;
		j=t;
		i=pre[j];
		while(j!=s)
		{
			f[i][j]+=min1;
			f[j][i]=-f[i][j];
			c[i][j]=G[i][j]-f[i][j];
			c[j][i]=G[j][i]-f[j][i];
			j=i;
			i=pre[j];
		}
	}
	return flow;
}

int main()
{
//	freopen("in.txt","r",stdin);
	int i,j,k,m,p,cc;
	int u,v,w;
	while(scanf("%d%d%d%d",&n,&p,&cc,&m)!=EOF)
	{
		memset(G,0,sizeof(G));
		while(m--)
		{
			scanf(" (%d,%d)%d ",&i,&j,&k);
			G[++i][++j]=k;
		}
		while(p--)
		{
			scanf(" (%d)%d ",&i,&j);
			G[0][++i]=j;
		}
		while(cc--)
		{
			scanf(" (%d)%d ",&i,&j);
			G[++i][n+1]=j;
		}
		memcpy(c,G,sizeof(G));
		printf("%d/n",ek(0,n+1));
	}
	return 0;
}

poj 1459（最大流）

Ta的文章更多 >>

热门文章

poj 1459（最大流）

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

Ta的文章更多 >>