南航省赛 optimum item choice.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>

#define NMAX 210
#define MAX 99999999
int c[NMAX][NMAX];
int f[NMAX][NMAX];
int q[NMAX*3];
int fa[NMAX]; 
int cost[NMAX];
int income[NMAX];

//南航省赛 Optimum item Choice
void printc(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			printf("%d ",c[i][j]);
		}
		printf("\n");
	}
}
void printf(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			printf("%d ",f[i][j]);
		}
		printf("\n");
	}
}
int get_maxliu(int start,int end,int num,int ans)
{
	int i,j,qs,qt,min;
	do
	{
		for(i=0;i<=num;i++) {fa[i]=q[i]=0;}
		fa[start]=-1;
		qs=0;qt=1;
		q[qt]=start;
		while(qs<qt && fa[end]==0)
		{
			i=q[++qs];
			for(j=1;j<=num;j++)
			{
				if(fa[j]==0)
				{
					if(c[i][j]>f[i][j])
					{
						q[++qt]=j;
						fa[j]=i;
					}
					else if(f[j][i]>0)
					{
						q[++qt]=j;
						fa[j]=-i;
					}
				}
			}
//			printf("(1)\n");
		}
		if(fa[end]!=0)
		{
			min=MAX;
			for(i=end;i!=start;i=abs(fa[i]))
			{
				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]];
				}
			}
			ans-=min;
			for(i=end;i!=start;i=abs(fa[i]))
			{
				if(fa[i]>0) f[fa[i]][i]+=min;
				else f[i][-fa[i]]-=min;
			}
//			printf(num);
//			system("pause");
//		printf("(2)\n");
		}
	}while(fa[end]!=0);
	return ans;
}

int solve(int num)
{
	int i,jnum,j,start,end,tt,ans=0;
//	printf("begin create\n");
	start=num+1;
	end=num+2;
	num+=2;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			f[i][j]=c[i][j]=0;
		}
	}
//	printf("begin create\n");
	for(i=1;i<=num-2;i++) scanf("%d",&cost[i]);
	for(i=1;i<=num-2;i++) scanf("%d",&income[i]);
//	printf("begin create\n");
	for(i=1;i<=num-2;i++)
	{
//		printf("%d:    %d\n end=%d",i,income[i]-cost[i],end);
		if(income[i]-cost[i]>0) 
		{
			c[start][i]=income[i]-cost[i];
			ans+=c[start][i];
		}
		else c[i][end]=cost[i]-income[i];
	}
	for(i=1;i<=num-2;i++)
	{
		scanf("%d",&jnum);
		for(j=1;j<=jnum;j++)
		{
			scanf("%d",&tt);
			c[i][tt]=MAX;
		}
	}
//	printc(num);
//	printf("create!\n");
//	system("pause");
	return get_maxliu(start,end,num,ans);
}

int main()
{
	int num,cnum=0;
	freopen("choice.in","r",stdin);
	freopen("choice.out","w",stdout);	
	while(scanf("%d",&num)!=EOF)
	{
		cnum++;
		printf("Case %d: %d\n",cnum,solve(num));
	}
}