poj1459.cpp

poj1459

#include "iostream"
#include "stdio.h"

#define maxn 104
using namespace std;

struct listtype
{
	int l,p;
};
struct nettype
{
	long c,f;
};

struct nettype g[maxn][maxn];
struct listtype lt[maxn];
int n,s,t;
long maxflow = 0;

/*
void readInfo()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
			scanf("%d",&g[i][j].c);
		lt[i].l = lt[i].p = 0;
	}
}
*/
int check()
{
	int i = 1;
	while((i <= n) && (!((lt[i].l != 0) && (lt[i].p == 0)))) i++;
	if(i > n) return 0;
	else return i;
}
int intabs(int k)
{
	if(k >= 0) return k;
	else return -k;
}
bool ford(long *a)
{
	int i,j,m;
	long x;
	bool ans = true;

	memset(lt,0,sizeof(lt));
	lt[s].l = s;
	do
	{
		i = check();
		if(i == 0) return ans;
	
		for(j = 1;j <= n;j++)
		{
			if((lt[j].l == 0) && ((g[i][j].c != 0) || (g[j][i].c != 0)))
			{
				if(g[i][j].f < g[i][j].c) lt[j].l = i;
				if(g[j][i].f > 0) lt[j].l = -i;
			}
		}
		lt[i].p = 1;
	}while(lt[t].l == 0);
	m = t;
	*a = 2100000000;
	do
	{
		j = m;
		m = intabs(lt[j].l);
		if(lt[j].l < 0) x = g[j][m].f - 0;
		if(lt[j].l > 0) x =g[m][j].c - g[m][j].f;
		if(*a > x) *a = x;
	}while(m != s);
	ans = false;
	return ans;
}
void fulkerson(long a)
{
	int m,j;
	m = t;
	maxflow += a;
	do
	{
		j = m;
		m = intabs(lt[j].l);
		if(lt[j].l < 0) g[j][m].f -= a;
		if(lt[j].l > 0) g[m][j].f += a;
	}while(m != s);
}

/*void printInfo()
{
	int i,j;
	cout<<"MaxFlow="<<maxflow<<endl;
	for(i = 1;i <= n;i++)
	{
		for(j = 1;j <= n;j++)
			cout<<g[i][j].f<<" ";
		cout<<endl;
	}

}*/
void deal(int a1,int b1)
{
	long del;
	bool succ;
	maxflow = 0;
	s = a1;
	t = b1;
	do
	{
		succ = ford(&del);
		if(succ != true) fulkerson(del);
	}while(succ != true);
	printf("%d\n",maxflow);
}
int main()
{
	int i, u, v, cc;
	int nn,np,nc,m;
	while (scanf("%d%d%d%d", &nn, &np, &nc, &m) == 4)
	{
		s = nn + 2; t = nn + 1;				//以下是构图
		memset(g,0,sizeof(g));
		for (i = 1; i <= m; i++)			//对于原图中边(u,v)连一条容量为cc的弧
		{
			while (getchar() != '(');
			scanf("%d,%d)%d", &u, &v, &cc);
			g[u + 1][v + 1].c = cc;
		}
		for (i = 1; i <= np; i++)			//对于PowerStation从源点连一条容量为cc的弧
		{
			while (getchar() != '(');
			scanf("%d)%d", &u, &cc);
			g[s][u + 1].c = cc;
		}
		for (i = 1; i <= nc; i++)			//对于Consumer连一条容量为cc的弧到汇点
		{
			while (getchar() != '(');
			scanf("%d)%d", &u, &cc);
			g[u + 1][t].c = cc;
		}
		n = nn + 2;
		memset(lt,0,sizeof(lt));
		deal(s,t);
									//求最大流
	}
	return 0;
}