#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 99999999

using namespace std;

int map[1005][1005],pre[1005];
vector<int>g[1005];
int n,m,S,T;

void build(int mid)
{
	int i,j;
	S=0;
	T=n+m+1;
	memset(map,0,sizeof(map));
	for(i=1;i<=n;i++)
		map[S][i]=1;
	for(i=1;i<=n;i++)
		for(j=0;j<g[i].size();j++)
			map[i][g[i][j]+n+1]=1;
	for(i=n+1;i<=n+m;i++)
		map[i][T]=mid;
}

bool bfs()
{
	int i,now;
	memset(pre,-1,sizeof(pre));
	queue<int>q;
	q.push(S);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(i=0;i<=T;i++)
		{
			if(pre[i]==-1&&map[now][i]>0)
			{
				pre[i]=now;
				if(i==T)
					return true;
				q.push(i);
			}
		}
	}
	return false;
}

int EK()
{
	int i,flow=0,min;
	while(bfs())
	{
		min=inf;
		for(i=T;i!=S;i=pre[i])
			if(map[pre[i]][i]<min)
				min=map[pre[i]][i];
//		printf("%d\n",min);
		for(i=T;i!=S;i=pre[i])
		{
			map[pre[i]][i]=map[pre[i]][i]-min;
			map[i][pre[i]]=map[i][pre[i]]+min;
		}
		flow=flow+min;
	}
	return flow;
}

void init()
{
	int i;
	for(i=0;i<1005;i++)
		g[i].clear();
}

int main()
{
	int i,j,left,right,mid;
	char str[100],c;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			break;
		init();
		for(i=1;i<=n;i++)
		{
			scanf("%s",str);
			while(1)
			{
				scanf("%d",&j);
				g[i].push_back(j);
				scanf("%c",&c);
				if(c=='\n')
					break;
			}
		}
		left=0;
		right=n;
		while(left<=right)
		{
			mid=(left+right)>>1;
			build(mid);
			int temp=EK();
			printf("%d %d\n",mid,temp);
			if(temp==n)
				right=mid-1;
			else
				left=mid+1;
		}
		printf("%d\n",left);
	}
	return 0;
}

• Re:为什么超时。。小菜鸟求解释。。。（附代码） (1927) lewabc 2011-08-11 18:22:54
  • Re:为什么超时。。小菜鸟求解释。。。（附代码） (34) lewabc 2011-08-11 18:23:37