|
Posted on 2010-08-18 21:37 acronix 阅读(144) 评论(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; }
|