HDOJ 4200 Bad Wiring 高斯消元

轉載請注明出處，謝謝http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove

慘痛的記憶，HDU第4次熱身賽的某題，很快有了算法，完成代碼。比賽期間花了3個小時在這題調試，晚上又花了兩個多小時對照官方資料調試。終于找到了問題。

還是經典的開關問題，受最近的影響，直接高斯消元解異或方程組，由于需要最少次數，枚舉自由變元即可，之前做的POJ 3185，類似的題目。可是POJ的資料弱了，當時沒有暴露出問題，結果在今天的比賽中坑爹了，無限的WA讓我十分郁悶。

之前的做法是找出自由變元的個數，對矩陣化簡，然後搜尋枚舉自由變元，結果發現自由變元所在列并不在最後幾列，這使得枚舉自由變元的時候出現了問題，囧，每次把目前全為0的列後移到最後，也就是自由變元。之後再枚舉

/*
ID:cxlove
PROB:poj 4200
DATA:2012.4.3
HINT:高斯消元法
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,d;
int a[105][105],cnt;
int ta[105][105],x[105],ans[105],var0;  
void debug(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
}
void dfs(int v){  
	if(v>n){  
		int temp=0;  
		for(int i=1;i<=n;i++)  
			x[i]=ans[i];  
		for(int i=1;i<=n;i++)  
			for(int j=1;j<=n+1;j++)  
				ta[i][j]=a[i][j];  		
		for(int i=var0-1;i>=1;i--){  
			for(int j=i+1;j<=n;j++)  
				ta[i][n+1]^=(x[j]&&ta[i][j]);  
			x[i]=ta[i][n+1];  
		}  
		for(int i=1;i<=n;i++)  
			if(x[i])  
				temp++;  
		cnt=min(temp,cnt);
	}  
	ans[v]=0;  
	dfs(v+1);  
	ans[v]=1;  
	dfs(v+1);  
}  
void gauss(){  
	int i,j,jj;  
	for(i=1,j=1,jj=1;i<=n&&jj<=n;jj++){ 
		int k=i;  
		for(;k<=n;k++)  
			if(a[k][j])  
				break;  
		if(a[k][j]){  
			for(int r=1;r<=n+1;r++)  
				swap(a[i][r],a[k][r]);  
			for(k=1;k<=n;k++)  
				if(k!=i&&a[k][j]){  
					for(int r=1;r<=n+1;r++)  
						a[k][r]^=a[i][r];  
				}  
				i++;  j++;
		} 
		else{
			int val=n-jj+j;
			for(int cow=1;cow<=n;cow++)
				swap(a[cow][j],a[cow][val]);
		}
	}  
	if(i==n+1){  
		cnt=0;  
		for(int r=1;r<=n;r++)  
			if(a[r][n+1])  
				cnt++;  
		printf("%d\n",cnt);  
		return ;  
	} 
	if(i<=n){
		for(int r=i;r<=n;r++)
			if(a[r][n+1]){
				printf("impossible\n");
				return ;
			}
	}
	var0=i;  
	cnt=1<<30;  
	dfs(i);  	
	printf("%d\n",cnt);  
}  
int main(){
	int t;
//	freopen("D.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&d);
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i][n+1]);
		for(int i=1;i<=n;i++)
			for(int j=max(1,i-d);j<=min(n,i+d);j++)
				a[i][j]=1;
		gauss();
	}
	return 0;
}