先DFS进行编号，然后用匈牙利算法求最大匹配.
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX=512;
int n,flag[MAX],link[MAX];
bool vst[MAX];
vector<int> g[MAX];
void init()
{
	memset(flag,-1,sizeof(flag));
	memset(link,-1,sizeof(link));
	for(int i=0;i<n;i++) g[i].clear();
}
void DFS(int ps,int dep){
	int i,len=g[ps].size();
	flag[ps]=dep;
	for(i=0;i<len;i++){
		int v=g[ps][i];
		if(flag[v]<0)
			DFS(v,1-dep);
	}
}
bool find(int a){
	int i,len=g[a].size();
	for(i=0;i<len;i++)
		if(!vst[i]){
			vst[i]=true;
			if(link[i]==-1||find(link[i])){
				link[i]=a;
				return true;
			}
		}
	return false;
}
int main()
{
	int i,j,num,tmp,id,ans;
	while(scanf("%d",&n)!=EOF){
		init();
		for(i=0;i<n;i++){
			scanf("%d: (%d)",&id,&num);
			for(j=0;j<num;j++){
				scanf("%d",&tmp);
				g[id].push_back(tmp);
			}
		}
		for(i=0;i<n;i++)
			if(flag[i]<0)
				DFS(i,0);
		ans=n;
		for(i=0;i<n;i++){
			if(!flag[i]){
				memset(vst,false,sizeof(vst));
				if(find(i)) ans--;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

• 不用看了,是我糊涂了 (20) a024014 2007-08-16 21:56:57