记录编号	369724	评测结果	AAAAAWAA
题目名称	[HAOI 2005]奇特的图案	最终得分	87
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.028 s
提交时间	2017-02-10 16:45:14	内存使用	4.16 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2010;
int n;
bool a[N][N],b[N],ans[N];
void solve(int x){
	if (x>n) return;
	if (!a[x][x]){
		for (int i=x;i<=n;i++)
		if (a[i][x]){
			for (int j=1;j<=n;j++) swap(a[x][j],a[i][j]);
			swap(b[x],b[i]);
			break;
		}
	}
	for (int i=x+1;i<=n;i++)
	if (a[i][x]){
		for (int j=1;j<=n;j++) a[i][j]^=a[x][j];
		b[i]^=b[x];
	}
	solve(x+1);
}
int Ans,sum;
void decide(int x){
	if (sum>Ans) return;
	if (a[x][x]&&ans[x]!=b[x]) return;
	sum+=ans[x];
	if (x==1){
		Ans=min(Ans,sum);
		return;
	}
	for (int i=1;i<=n;i++)
		if (a[i][x]) b[i]^=ans[x];
	ans[x-1]=0;
	decide(x-1);
	ans[x-1]=1;
	decide(x-1);
	for (int i=1;i<=n;i++)
		if (a[i][x]) b[i]^=ans[i];
	return;
}
char s[10010],*ch;
int read(){
	int x=0;
	while (*ch&&(*ch>'9'||*ch<'0')) ++ch;
	while (*ch>='0'&&*ch<='9') x=x*10+*ch-'0',++ch;
	return x;
}
int main()
{
	freopen("t3.in","r",stdin);
	freopen("t3.out","w",stdout);
	scanf("%d",&n);gets(s);
	for (int i=1;i<=n;i++){
		gets(s);ch=s;
		b[i]=!read();
		a[i][i]=1;
		while (1){
			int x=read();
			if (!x) break;
			a[x][i]=1;
		}
	}
	solve(1);
	Ans=n;
	ans[n]=0;decide(n);
	ans[n]=1;decide(n);
	printf("%d\n",Ans);
	return 0;
}