1518: 熄灯的工作
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 471  Solved: 19
[Submit][Status][Web Board]
Description
重庆游戏与电子竞技大学的熄灯时间是11点半。每天晚上，宿管嬢嬢都是用总开关来关灯的。但是今天总开关坏了，只有一些分开关，每个开关控制一些灯，灯都有可能被多个开关控制。按一次开关，所有它所控制的灯都会切换一次状态，即亮的灯变灭，灭的灯变亮。一开始所有灯都是亮的，宿管嬢嬢想把所有的灯都灭了，但是她面对一堆开关头皮发麻，只好找来了头铁的你来解决这个问题。
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个正整数，表示灯的数量N(1<=N<=100)和开关的数量M(1<=M<=100)。灯的编号从1到N。 接下来M行，每行的开头是一个整数，表示这个开关控制的灯的数量X(0<=X<=N)，接下来是X个不相同的数字，表示这个开关控制的灯的编号。
Output
如果可以用这些开关关掉所有灯，输出”YES”。否则，输出”NO”。
Sample Input
3 2
2 1 2
2 1 3
Sample Output
NO

学了一下高斯消元，异或方程还挺有意思的

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[202][202]={0};
void gauss()
{
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(j<=n&&!a[j][i]) j++;
		if(j>n) continue;
		if(i!=j) for(int k=1;k<=m+1;k++) swap(a[i][k],a[j][k]);
		for(int l=1;l<=n;l++)
			if(l!=i&&a[l][i])
				for(int k=1;k<=m+1;k++) a[l][k]^=a[i][k];
	}
}
int main()
{
	int ans=1;
	scanf("%d%d",&n,&m);
	//a[n][m];
	for(int i=1;i<=n;i++) a[i][m+1]=1;
	for(int i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		for(int j=1;j<=x;j++)
		{
			int t;
			scanf("%d",&t);
			a[t][i]=1;
		}
	}
	gauss();
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=m+1;j++)
		{
			if(a[i][j]&&j!=m+1) break;
			if(a[i][j]&&j==m+1)
			{
				printf("NO");
				return 0;
			}
		}	
	}
	printf("YES");
	
}