#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
#include<vector>
#define min(a,b) (a)<(b)?(a):(b)

using namespace std;

struct node
{
	int to,ca,re;
};

typedef vector<node> edge;

edge G[1000];
bool used[1000];

void add_edge(int s,int t,int c)
{
	G[s].push_back((node){t,c,G[t].size()});
	G[t].push_back((node){s,0,G[s].size()-1});
}

int dfs(int v,int t,int f)
{
	if(v==t) return f;
	used[v]=true;
	for(int i=0;i<G[v].size();i++)
	{
		if(!used[G[v][i].to]&&G[v][i].ca>0)
		{
			int d=dfs(G[v][i].to,t,min(G[v][i].ca,f));
			if(d>0)
			{
				//printf("%d ",v);
				G[v][i].ca-=d;
				G[G[v][i].to][G[v][i].re].ca+=d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s,int t)
{
	int flow=0;
	while(true)
	{
		memset(used,false,sizeof(used));
		int f=dfs(s,t,INT_MAX);
		//printf("\n");
		if(f==0) return flow;
		flow+=f;
	}
}

int main()
{
	/*add_edge(0,1,10);
	add_edge(0,2,2);
	add_edge(1,2,6);
	add_edge(1,3,6);
	add_edge(2,4,5);
	add_edge(3,2,3);
	add_edge(3,4,8);
	printf("%d",max_flow(0,4));*/
	int n,f,d;
	scanf("%d%d%d",&n,&f,&d);
	int s=n*2+d+f,t=n*2+d+f+1;
	for(int i=0;i<f;i++)
	{
		add_edge(s,n*2+i,1);
	}
	for(int i=0;i<d;i++)
	{
		add_edge(n+2+f+i,t,1);
	}
	for(int i=0;i<n;i++)
	{
		add_edge(i,n+i,1);
		int tf,td;
		scanf("%d%d",&tf,&td);
		for(int j=0;j<tf;j++)
		{
			int tmp;
			scanf("%d",&tmp);tmp--;
			add_edge(n*2+tmp,i,1);
		}
		for(int j=0;j<td;j++)
		{
			int tmp;
			scanf("%d",&tmp);tmp--;
			add_edge(n+i,n*2+f+tmp,1);
		}
	}
	/*for(int i=0;i<n*2+f+d+2;i++)
	{
		printf("%d|",i);
		for(int j=0;j<G[i].size();j++)
		{
			printf("%d ",G[i][j].to);
		}
		printf("\n");
	}*/
	printf("%d\n",max_flow(s,t));
}

• Re:哪里WA了 求大神指教 (1998) rabbit_lb 2016-05-31 19:58:53
  • Re:哪里WA了 求大神指教 (10) rabbit_lb 2016-05-31 19:59:46
    • Re:哪里WA了 求大神指教 (14) rabbit_lb 2016-05-31 19:59:50
      • Re:哪里WA了 求大神指教 (0) rabbit_lb 2016-05-31 19:59:52