UVa 10330 Power Transmission / 最大流

最大流这题有很多起点和终点在取2个点（0和n+1）作为唯一的起点和终点

此外每个点也有容量限制建图时每条边上的容量为这条边和2个端的容量的最小值然后EK就行

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int MAX = 110;

int num[MAX];

int a[MAX];

int cap[MAX][MAX];

int flow[MAX][MAX];

int p[MAX];

int n,m,b,d;

int f;

void EK()

{

	queue <int> q;

	memset(flow,0,sizeof(flow));

	f = 0;

	while(1)

	{

		memset(a,0,sizeof(a));

		a[0] = 999999999;

		q.push(0);

		while(!q.empty())

		{

			int u = q.front();

			q.pop();

			for(int v = 0; v <= n+1; v++)

			{

				if(!a[v] && cap[u][v] > flow[u][v])

				{

				p[v] = u;

				q.push(v);

				a[v] = min(a[u],cap[u][v] - flow[u][v]);

				}

			}

		}

		if(a[n+1] == 0)

			break;

		for(int u = n+1; u; u = p[u])

		{

			flow[p[u]][u] += a[n+1];

			flow[u][p[u]] -= a[n+1];

		}

		f += a[n+1];

	}

}

int main()

{

	int i,x,y,z;

	while(scanf("%d",&n)!=EOF)

	{

		memset(cap,0,sizeof(cap));

		for(i = 1;i <= n; i++)

		scanf("%d",&num[i]);

		scanf("%d",&m);

		while(m--)

		{

			scanf("%d %d %d",&x,&y,&z);

			cap[x][y] = z;

			cap[x][y] = min(cap[x][y],min(num[x],num[y]));

		}

		scanf("%d %d",&b,&d);

		while(b--)

		{

			scanf("%d",&x);

			cap[0][x] = num[x];

		}

		while(d--)

		{

			scanf("%d",&x);

			cap[x][n+1] = num[x];

		}

		EK();

		printf("%d\n",f);

	}

	return 0;

}

巴特西

UVa 10330 Power Transmission / 最大流

最新文章

热门文章