noj 1044 dining.txt

ACM资料大集合

//#include <iostream>
#include <stdio.h>
//include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <time.h>
//using namespace std;

//NOJ 1044 Dining
//增广路 预留推进
#define DIANMAX 420
#define NMAX 102
#define MAX 100
#define FMAX 102
#define DMAX 102

/*
4 5 1 4
1 2 6
1 3 5
2 3 2
2 4 5
3 4 9


4 5 1 4
1 2 6
1 3 4
2 3 3
2 4 4
3 4 8

4 5 1 4
1 2 7
1 3 2
2 3 3
2 4 1
3 4 5

输出：
11
10
6
*/
int F_like[NMAX];
int D_like[NMAX];
int F_i[NMAX][FMAX];
int D_i[NMAX][DMAX];
int high[DIANMAX];

int c[DIANMAX][DIANMAX];
int fa[DIANMAX];//??????????,????????????????????????????????????????????????????????????????
int f[DIANMAX][DIANMAX];//??????????????????
int q[DIANMAX*100];//????
int e[DIANMAX];
int h[DIANMAX];

void init(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			f[i][j]=0;
			c[i][j]=0;
		}
	}
}

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			printf("%2d",f[i][j]);
		}
		printf("\n");
	}
}

int get_maxliu(int start,int end,int num)
{
	int flag,has,i,tt,j,min;
	
	for(i=1;i<=num;i++)
	{
		e[i]=0;
		h[i]=0;
	}
	h[start]=num;
	for(i=1;i<=num;i++)
	{
		if(c[start][i]>0)
		{
			e[start]-=c[start][i];
			e[i]+=c[start][i];
			f[start][i]=c[start][i];
			f[i][start]=-c[start][i];
		}
	}
	flag=1;
	while(flag==1)
	{
		flag=0;
		for(i=1;i<=num;i++)
		{
			if(e[i]>0&&i!=end)
			{
				flag=1;has=0;min=MAX*MAX;
				for(j=1;j<=num;j++)
				{
					if(c[i][j] > f[i][j])
					{
						if(h[i]==h[j]+1)
						{
							has=1;
							if(c[i][j]-f[i][j]<e[i]) tt=c[i][j]-f[i][j];
							else tt=e[i];
							e[i]-=tt;
							e[j]+=tt;
							f[i][j]+=tt;
							f[j][i]-=tt;							
						}
						else
						{
							if(min>h[j]+1) min=h[j]+1;
						}
					}
				}
				if(has==0) h[i]=min;
			}
		}
	}
	return e[end];
}

/*
int get_maxliu(int start,int end,int num)
{
	int ans=0,i,j,qs,qt,min;
	fa[end]=1;
	int k=0;
	while(fa[end]!=0)
	{
		for(i=0;i<=num;i++)
		{
			fa[i]=q[i]=0;
		}
		fa[start]=-1;
		qs=0;qt=1;
		q[qt]=start;
//		printf("(1) %d\n",++k);
		while(qs<qt && fa[end]==0)
		{
			i=q[++qs];
//			printf("(2) i=%d\n",i);
			for(j=1;j<=num;j++)
			{
				if(fa[j]==0)
				{
					if(c[i][j]>f[i][j]) 
					{
						q[++qt]=j;
						fa[j]=i;
//						printf("(3) j=%d\n",j);
					}
					else if(f[j][i]>0)
					{
						q[++qt]=j;
						fa[j]=-i;
//						printf("(3) j=%d\n",j);
					}
				}
			}
//			printf("(4) find qian qu\n");
//			system("pause");
		}
		if(fa[end]!=0)
		{
			min=MAX;
			i=end;
			while(i!=start)
			{
				if(fa[i]>0)
				{
					if(min>c[fa[i]][i]-f[fa[i]][i]) min=c[fa[i]][i]-f[fa[i]][i];
				}
				else
				{
					if(min>f[i][fa[i]]) min=f[i][-fa[i]];
				}
				i=abs(fa[i]);
			}
			ans+=min;
			i=end;
			while(i!=start)
			{
				if(fa[i]>0) f[fa[i]][i]+=min;
				else f[i][-fa[i]]-=min;
				i=abs(fa[i]);
			}
		}
//		system("pause");
	}
	return ans;
}
*/
int create(int N,int F,int D)
{
    int start,food,drink,end,i,j,cowf,cowd;
    start=food=1;
    cowf=food+F;
    cowd=cowf+N;
    drink=cowd+N;
    end=drink+D+1;
    for(i=1;i<=F;i++)
        c[start][start+i]=1;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=F_like[i];j++)
            c[F_i[i][j]+food][cowf+i]=1;
        for(j=1;j<=D_like[i];j++)
            c[cowd+i][D_i[i][j]+drink]=1;
    }
    for(i=1;i<=N;i++)
        c[cowf+i][cowd+i]=1;
    for(i=1;i<=D;i++)
        c[drink+i][end]=1;
    return end;
}

int main()
{
    int N,F,D,i,j,huidian;
    scanf("%d%d%d",&N,&F,&D);
    for(i=1;i<=N;i++)
    {
        scanf("%d%d",&F_like[i],&D_like[i]);
        for(j=1;j<=F_like[i];j++)
            scanf("%d",&F_i[i][j]);
        for(j=1;j<=D_like[i];j++)
            scanf("%d",&D_i[i][j]);
    }
    huidian=create(N,F,D);
    printf("%d\n",get_maxliu(1,huidian,huidian));
    return 0;
}
/*


int main()
{
	int num,pnum,i,ta,tb,tc,start,end;
	while(scanf("%d%d%d%d",&num,&pnum,&start,&end)!=EOF)
	{
		init(num);
		for(i=0;i<pnum;i++) 
		{
			scanf("%d%d%d",&ta,&tb,&tc);
			c[ta][tb]=tc;
		}
		printf("%d\n",get_maxliu(start,end,num));
	}
	return 0;
}

*/