#include<stdio.h>
#include<string.h>
#include<iostream>
#include<memory.h>
#include<queue>
#include<cstdio>
#include <cmath>

using namespace std;

#define MAXN 110
#define INF 999999999
int n,np,nc,m;
int cap[MAXN][MAXN],father[MAXN],res;
int start,end;
queue<int>q;

void maxflow()
{
	int x,i,temp,ok;
	
	while(1)
	{
		ok=0;
		for(i=0;i<=end;i++)
			father[i]=-1;
		
		q.push(start);
		temp=INF;
		while(!q.empty())
		{
			x=q.front();
			q.pop();
			for(i=0;i<=end;i++)
			{
				if(father[i]==-1&&cap[x][i]>0)
				{
					if(i==end)
						ok=1;
					father[i]=x;
					temp=temp<cap[x][i]?temp:cap[x][i];
					
					q.push(i);
				}
			}
		}
		if(!ok)  break;
		
		for(i=end;i!=0;i=father[i])
		{
			cap[father[i]][i]-=temp;
			cap[i][father[i]]+=temp;
		}
		res+=temp;
	}
	return ;
}

int main()
{
	int i,j,a,b,c;
	char s[30];
	while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
	{
		start=0;
		end=n+1;
		for(i=0;i<=end;i++)
			for(j=0;j<=end;j++)
				cap[i][j]=0;
		for(i=0;i<m;i++)
		{
			scanf("%s",s);
			sscanf(s,"(%d,%d)%d",&a,&b,&c);
			cap[a+1][b+1]+=c;
		}
		for(i=0;i<np;i++)
		{
			scanf("%s",s);
			sscanf(s,"(%d)%d",&a,&b);
			cap[start][a+1]+=b;
		}
		for(i=0;i<nc;i++)
		{
			scanf("%s",s);
			sscanf(s,"(%d)%d",&a,&b);
			cap[a+1][end]+=b;
		}
		res=0;
		maxflow();
		printf("%d\n",res);
	}
	return 0;
}

• 找到了，但不知道为什么，以下是改过的代码，只是加了flow[MAXN][MAXN],v[maxn]两个数组 (1450) zl_leaf 2012-04-19 14:07:24