2281097_ac_45ms_288k.cc

北大大牛代码 1240道题的原代码 超级权威

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

int N, B, ans;
int map[1001][21];
int lik[1001][21];
int cap[21], b[21], tmp[21];
int link[21][1010];

void input()
{
	int i, j;

	scanf("%d%d",&N,&B);
	for(i = 0; i < N; i++)
		for(j = 0; j < B; j++)
			scanf("%d",&lik[i][j]);
	for(i = 1; i <= B; i++)
		scanf("%d",&tmp[i]);
}

int create(int i, int n)
{
	int j, k, sum = 0;
	int mark[21];

	memset(mark,0,sizeof(mark));
	for(j = 1; j <= B; j++)
		cap[j] = tmp[j];
	memset(map,0,sizeof(map));
	for(j = 0; j < N; j++)
	{
		for(k = i; k <= i+n; k++)
		{
			if(mark[lik[j][k]]==0)
				sum += tmp[lik[j][k]],mark[lik[j][k]] = 1;
			map[j+1][lik[j][k]] = 1;
		}
	}
	if(sum<N)
		return 0;
	return 1;
}

int find(int v)
{
	int i, j;

	for(i = 1; i <= B; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(cap[i])
			{
				cap[i]--;
				link[i][++link[i][0]] = v;
				return 1;
			}
			else
			{
				for(j = 1; j <= link[i][0]; j++)
					if(find(link[i][j]))
					{
						link[i][j] = v;
						return 1;
					}
			}
		}
	}
	return 0;
}

int match()
{
	int i;

	ans = 0;
	memset(link,0,sizeof(link));
	for(i = 1; i <= N; i++)
	{
		memset(b,0,sizeof(b));
		if(find(i))
			ans++;
	}
	return ans;
}

void solve()
{
	int i;
	int n = 1;

	for(n = 0; n < B; n++)
	{
		for(i = 0; i < B-n; i++)
		{
			if(!create(i,n))
				continue;
			if(match()==N)
			{
				printf("%d\n",n+1);
				return ;
			}
		}
	}
}

int main()
{
	input();
	solve();
	return 1;
}