Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

qiuzhu wrong answer

Posted by chr32 at 2014-12-18 13:16:58 on Problem 3281
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator