| ||||||||||
| 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