> #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:为什么超时。。小菜鸟求解释。。。（附代码） (34) lewabc 2011-08-11 18:23:37