Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
qiuzhu wrong answer#include<algorithm> #include<iostream> #include<stdio.h> using namespace std; struct edg { long r,y,next,op; }; edg g[10000]; long h[10000],n,m,tot,ans1,cow,food,drink; long level[10000]; bool bfs() { long o[10000]; // memset(o,0,sizeof(o)); long f=1;long l=1; o[0]=1; memset(level,0,sizeof(level)); level[1]=0; do { for(int i=h[o[f]];i!=0;i=g[i].next) { long u=g[i].y; if(level[u]==0&&g[i].r!=0) { level[u]=level[o[f]]+1; l++; o[l]=u; if(u==n)return true; } } f++; } while(l>=f); return false; } int dfs(long u,long a) { if(u==n||a==0)return a; long ans=0; for(long i=h[u];i>0;i=g[i].next) { long v=g[i].y; long val=g[i].r; if(level[v]==level[u]+1) { long flow=dfs(v,min(a,val)); if(flow!=0) { g[i].r=g[i].r-flow; g[g[i].op].r=g[g[i].op].r+flow; ans=ans+flow; a=a-flow; if(a==0)break; } } } return ans; } void add(long a,long b,long c) { tot++; g[tot].y=b; g[tot].r=c; g[tot].next=h[a]; h[a]=tot; g[tot].op=tot+1; tot++; g[tot].y=a; g[tot].r=0; g[tot].next=h[b]; h[b]=tot; g[tot].op=tot-1; } int main() { freopen("b.in","r",stdin); long x,y,z; while(~scanf("%d%d%d",&cow,&food,&drink)) { n=cow+food+drink+1; for(int i=1;i<=cow;i++) { scanf("%d%d",&x,&y); for(int j=1;j<=x;j++) { scanf("%d",&z); add(i,z+cow,1); } for(int j=1;j<=y;j++) { scanf("%d",&z); add(z+cow+food,i,1); } } for(long i=1;i<=drink;i++)add(0,i+cow+food,1); for(long i=1;i<=food;i++)add(i+cow,n,1); while(bfs()) { ans1=ans1+dfs(0,n); } printf("%d\n",ans1); ans1=0; memset(h,0,sizeof(h)); tot=0; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator