poj 3185 The Water Bowls 高斯消元

经典开关问题，不过这回给出的是一行开关而不是矩阵开关。高斯消元枚举自由变元

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int n = 20;
int a[22][22] , x[22], freex[22],xx[22];
void debug()
{
	puts("debug");
	int i,j;
	for(i = 0;i < n; i++)
	{
		for(j = 0;j < n+1;j ++)
			printf("%d ",a[i][j]);
		puts("");
	}
	puts("end");
}
void gauss()
{
	int i,j,l;
	int row = 0, col = 0;
//	debug();
	for(; row < n && col < n; row++, col++)
	{
		int maxr = row;
		for(i = row+1;i < n; i++)
			if(a[i][col])
				maxr = i;
		if(!a[maxr][col])
		{
			row --;
			continue;
		}
		if(row != maxr)
			for(i = col;i < n+1;i ++)
				swap(a[maxr][i] , a[row][i]);
		for(i = row+1;i < n ;i++)
			if(a[i][col])
				for(j = col;j < n+1; j++)
					a[i][j] ^= a[row][j];
	}
//	debug();
	int ans = 0;
	for(i = n-1;i >= 0; i--)
	{
		x[i] = a[i][n];
		for(j = i+1;j < n; j++)
			if(x[j] && a[i][j])
				x[i] ^= 1;
		if(x[i])
			ans ++;
	}
	for(i = 0;i < n; i++)
		freex[i] = 1;
	for(i = row-1;i >= 0; i--)
	{
		int num = 0 , id;
		for(j = i;j < n; j++)
			if(a[i][j] && freex[j])
				num ++ , id = j;
		if(num > 1)
			continue;
		x[id] = a[i][n];
		for(j = id+1;j < n; j++)
			if(a[i][j])
				x[id] ^= 1;
		freex[id] = 0;
	}
	int num = 0;
	int k = n-row;
	int N = 1<<k;
	for(i = n-1;i >= 0 && num < k;i--)
		if(freex[i])
			xx[num++] = i;
	for(j = i;j >= 0; j--)
		freex[i] = 0;
	for(i = 0;i < N; i++)
	{
		int sum = 0;
		for(j = 0;j < k; j++)
			if(i & (1<<j))
				x[xx[j]] = 1,sum++;
			else
				x[xx[j]] = 0;
		for(j = row-1;j >= 0;j --)
		{
			for(l = j;l < n; l++)
				if(a[j][l])
					break;
			int id = l;
			x[id] = a[j][n];
			for(l = id+1;l < n; l++)
				if(a[j][l] && x[l])
					x[id] ^= 1;
			if(x[id])
				sum++;
		}
		if(sum < ans)
			ans = sum;
	}
	printf("%d\n", ans);
}
int main()
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0;i < n; i++)
		scanf("%d", &a[i][20]);
	for(i = 0;i < n ;i++)
	{
		a[i][i] = 1;
		if(i > 0)
			a[i][i-1] = 1;
		if(i < n-1)
			a[i][i+1] = 1;
	}
	gauss();
	return 0;
}