转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
一如既往,继续高斯,这题和之前的略有不同,需要考虑多组解的情况。
当出现自由变元时,枚举所有解,取最优解。开始尝试用位运算,后来果断搜索吧。
不过这题貌似有问题,详见
http://blog.csdn.net/acm_cxlove/article/details/7424358
/*
ID:cxlove
PROB:poj 3185
DATA:2012.4.1
HINT:高斯消元+枚举变元
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[25][25],ans[25],var,var0,cnt;
int x[25];
void debug(){
for(int i=0;i<20;i++){
for(int j=0;j<20;j++)
printf("%d ",a[i][j]);
printf("%d\n",a[i][20]);
}
}
int ta[25][25];
void dfs(int v){
if(v==20){
int temp=0;
for(int i=0;i<20;i++)
x[i]=ans[i];
for(int i=0;i<20;i++)
for(int j=0;j<=20;j++)
ta[i][j]=a[i][j];
for(int i=var0-1;i>=0;i--){
for(int j=i+1;j<20;j++)
ta[i][20]^=(x[j]&&ta[i][j]);
x[i]=ta[i][20];
}
for(int i=0;i<20;i++)
if(x[i])
temp++;
cnt=min(cnt,temp);
return ;
}
ans[v]=0;
dfs(v+1);
ans[v]=1;
dfs(v+1);
}
void gauss(){
int i,j;
for(i=0,j=0;i<20&&j<20;j++){
int k=i;
for(;k<20;k++)
if(a[k][j])
break;
if(a[k][j]){
for(int r=0;r<=20;r++)
swap(a[i][r],a[k][r]);
for(int k=0;k<20;k++)
if(k!=i&&a[k][j]){
for(int r=0;r<=20;r++)
a[k][r]^=a[i][r];
}
i++;
}
}
if(i==20){
cnt=0;
for(int r=0;r<20;r++)
if(a[r][20])
cnt++;
printf("%d\n",cnt);
return ;
}
var0=i;
cnt=100;
dfs(var0);
printf("%d\n",cnt);
}
int main(){
memset(a,0,sizeof(a));
for(int i=0;i<20;i++)
scanf("%d",&a[i][20]);
for(int i=0;i<20;i++){
a[i][i]=1;
a[max(0,i-1)][i]=1;
a[min(19,i+1)][i]=1;
}
gauss();
return 0;
}
分享到:
相关推荐
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
poj 1611 The Suspects 代码 并查集的应用
北大POJ2187-Beauty Contest 解题报告+AC代码
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码
北大POJ1019-Number Sequence 解题报告+AC代码
北大POJ3126-Prime Path 解题报告+AC代码