记录编号	602722	评测结果	A
题目名称	2997.[POJ 1463]战略游戏	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.097 s
提交时间	2025-07-05 15:51:23	内存使用	3.99 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=3000;
int n;
int nxt[N],hd[N],v[N],match[N],tot,ans;
bool vis[N];
void add(int x,int y){
	++tot;
	nxt[tot]=hd[x];
	v[tot]=y;
	hd[x]=tot;
}
bool dfs(int x){
	for(int i=hd[x],y;i;i=nxt[i]){
		y=v[i];
		if(!vis[y]){
			vis[y]=1;
			if(!match[y]||dfs(match[y])){
				match[y]=x;
				return true;
			}
		}
	}
	return false;
}
void solve(){
	tot=ans=0;
	memset(nxt,0,sizeof(nxt));
	memset(hd,0,sizeof(hd));
	memset(v,0,sizeof(v));
	memset(match,0,sizeof(match));
	for(int i=1;i<=n;i++){
		int x,size;
		scanf("%d:(%d)",&x,&size);
		x++;
		for(int j=1;j<=size;j++){
			int y;
			scanf("%d",&y);
			y++;
			add(x,y);
			add(y,x);
		}
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(dfs(i)) ans++;
	}
	printf("%d\n",ans>>1);
	return;
}
int main(){
	freopen("strategic.in","r",stdin);
	freopen("strategic.out","w",stdout);
	while(cin>>n){
		solve();
	}
	return 0;
}