poj1681 高斯消元+dfs枚举

wa  N多次后，终于把高斯消元的模板给弄出来了，并且精简了许多。

用dfs枚举变元比二进制枚举变元简单多了。

（也终于明白 变元代表只得解的个数。）

上模板。

#include <iostream>
#include <algorithm>
using namespace std;
int a[400][400];
int ans[400],x[400];//ans[]用于记录哪几种情况。x[]保存结果。
int equ,var,cnt,var0;
void dfs(int v)
{
	if(v==var)  //将多个解的情况枚举出来就可以当成是“唯一解”处理了。
	{
		int temp=0;
		memcpy(x,ans,sizeof(ans));  //唯一多的一条语句。
		for(int i=var0-1;i>=0;i--)  //开始位置不一样。未被遍历的，已经从ans[]拷贝过来了。
		{
			x[i]=a[i][var];
			for(int j=i+1;j<var;j++)
				x[i]^=(x[j]&&a[i][j]);
		}
		for(int i=0;i<var;i++)
			temp+=x[i];
		cnt=min(temp,cnt);
		return ;
	}
	ans[v]=0;  //解的个数为 1<<var-var0;
	dfs(v+1);  //枚举。
	ans[v]=1;
	dfs(v+1);
}
void gauss()
{
	int h=0,col=0;
	for(;col<var&&h<equ;col++)
	{
		int k=h;
		for(int i=h+1;i<equ;i++)
			if(abs(a[i][col])>abs(a[k][col]))
				k=i;
		if(a[k][col])
		{
			for(int r=col;r<=var;r++)
				swap(a[h][r],a[k][r]);
			for(int i=h+1;i<equ;i++)
				if(a[i][col])
					for(int r=col;r<=var;r++)
						a[i][r]^=a[h][r];
			h++;
		}
	}
	for(int i=h;i<equ;i++)  //无解的情况。
		if(a[i][col])
		{
			cout<<"inf\n";
			return ;
		}
	if(h==var)  //唯一解。
	{
		cnt=0;
		for(int i=var-1;i>=0;i--)  
		{
			x[i]=a[i][var];   
			for(int j=i+1;j<var;j++)
				x[i]^=(x[j]&&a[i][j]);
			cnt+=x[i];
		}
		cout<<cnt<<endl;
		return ;
	}
	cnt=1111111;     //多个解。
	var0=h;
	dfs(var0);
	cout<<cnt<<endl;
	return ;
}
void init(int n)
{
	equ=var=n*n;
	memset(a,0,sizeof(a));
	for(int i=0;i<n*n;i++)
	{
		a[i][i]=1;
		if(i%n!=0)
			a[i-1][i]=1;
		if(i%n!=n-1)
			a[i+1][i]=1;
		if(i>=n)
			a[i-n][i]=1;
		if(i+n<n*n)
			a[i+n][i]=1;
		}
}
int main()
{
	int cas;
	cin>>cas;
	while(cas--)
	{
		int n;
		char ch;
		cin>>n;
		init(n);
		for(int i=0;i<n*n;i++)
		{
			cin>>ch;
			a[i][n*n]=ch==‘w‘;
		}
		gauss();
	}
	return 0;
}

poj1681 高斯消元+dfs枚举,布布扣,bubuko.com

poj1681 高斯消元+dfs枚举

原文：http://blog.csdn.net/u012915516/article/details/23793133