POJ 3185 The Water Bowls(高斯消元)

题目地址：POJ 3185

         醉了。，。高斯消元这种题样例都不过的时候怎么调试好。。。干瞪着看了半天代码终于发现是一个符合写错了。。

        这题同样是高斯消元+自由元枚举。没什么好说的。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
int b[31], a[30][30];
int free_num, free_x[30], state[30];
int gauss()
{
        int i, j, k, h, max_r, tmp;
        free_num=0;
        for(i=0,j=0;i<20&&j<20;i++,j++){
                max_r=i;
                for(k=i+1;k<20;k++){
                        if(a[k][j]>a[max_r][j]) max_r=k;
                }
                if(max_r!=i){
                        for(k=j;k<=20;k++){
                                swap(a[i][k],a[max_r][k]);
                        }
                }
                if(!a[i][j]){
                        free_x[free_num++]=j;
                        i--;
                        continue ;
                }
                for(k=i+1;k<20;k++){
                        if(a[k][j]==0) continue ;
                        for(h=j;h<21;h++){
                                a[k][h]^=a[i][h];
                        }
                }
        }
        //printf("%d\n",free_num);
        tmp=i;
        for(i=tmp;i<20;i++){
                if(a[i][20])
                        return INF;
        }
        int tot=1<<free_num, cnt, ans=INF;
        //printf("%d\n",tot);
        for(i=0;i<tot;i++){
                cnt=0;
                for(j=0;j<free_num;j++){
                        if(i&(1<<j)){
                                state[free_x[j]]=1;
                                cnt++;
                        }
                        else{
                                state[free_x[j]]=0;
                        }
                }
                for(j=tmp-1;j>=0;j--){
                        int t=0;
                        while(a[j][t]==0) t++;
                        state[t]=a[j][20];
                        for(k=t+1;k<20;k++){
                                if(a[j][k]) state[t]^=state[k];
                        }
                        cnt+=state[t];
                }
                //printf("--%d\n",cnt);
                ans=min(ans,cnt);
        }
        return ans;
}
int main()
{
        int i;
        for(i=0;i<20;i++){
                scanf("%d",&b[i]);
        }
        memset(a,0,sizeof(a));
        for(i=0;i<20;i++){
                a[i][i]=1;
                if(i) a[i][i-1]=1;
                if(i!=19) a[i][i+1]=1;
                a[i][20]=b[i];
        }
        printf("%d\n",gauss());
        return 0;
}

POJ 3185 The Water Bowls(高斯消元)

原文：http://blog.csdn.net/scf0920/article/details/43197207