|
|
Posted on 2010-08-18 21:37 acronix 阅读(145) 评论(0) 编辑 收藏 引用 所属分类: hzshuai解题报告
先上代码：
 
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <string.h>
using namespace std;
const int inf = 0x7ffffff;
#define Max 410
int flow[Max][Max],d[Max]; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0;
int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0;i<=N;i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end)
return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i] -= a;
flow[i][k] += a;
sum -= a;
}
return os-sum;
}
int main()
{
int i,j,n,np,nc,m;
int x,y,v;
char s[20],*p;
while (scanf("%d %d %d %d",&n,&np,&nc,&m) != EOF)
{
sta = n; end = N = n + 1;
memset(flow,0,sizeof(flow));
for (i = 1; i <= m; i++)
{
scanf("%s",s);
p = s + 1;
sscanf(p,"%d",&x);
p = strchr(p,',') + 1;
sscanf(p,"%d",&y);
p = strchr(p,')') + 1;
sscanf(p,"%d",&v);
flow[x][y] += v;
}
for (i = 1; i <= np; i++)
{
scanf("%s",s);
p = s + 1;
sscanf(p,"%d",&x);
p = strchr(p,')') + 1;
sscanf(p,"%d",&v);
flow[sta][x] = v;
}
for (i = 1; i <= nc; i++)
{
scanf("%s",s);
p = s + 1;
sscanf(p,"%d",&x);
p = strchr(p,')') + 1;
sscanf(p,"%d",&v);
flow[x][end] = v;
}
int ret = 0;
while(bfs(sta))
ret += dinic(sta,inf);
printf("%d\n",ret);
}
return 0;
}
|