[Gauss]POJ3185 The Water Bowls

  1 int a[300][300];  // 增广矩阵
  2 int x[300];  // 解
  3 int free_x[300]; // 标记是否为自由未知量
  4 
  5 int n;
  6 void debug()
  7 {
  8     for(int i=0;i<n*n;i++)
  9     {
 10         for(int j=0;j<n*n;j++)
 11             printf("%d ", a[i][j]);
 12         printf("\n");
 13     }
 14 }
 15 
 16 int Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列
 17 {
 18     //转换为阶梯形式
 19     int col=0, k, num=0;
 20     for(k=0;k<n && col<m;k++, col++)
 21     {//枚举行
 22         int max_r=k;
 23         for(int i=k+1;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换
 24             if(abs(a[i][col])>abs(a[max_r][col]))
 25                 max_r=i;
 26         if(max_r!=k)// 与第k行交换
 27             for(int j=col;j<m+1;j++)
 28                 swap(a[k][j], a[max_r][j]);
 29         if(!a[k][col])// 说明该col列第k行以下全是0了
 30         {
 31             k--;
 32             free_x[num++]=col;
 33             continue;
 34         }
 35         for(int i=k+1;i<n;i++)// 枚举要删除的行
 36             if(a[i][col])
 37                 for(int j=col;j<m+1;j++)
 38                     a[i][j]^=a[k][j];
 39     }
 40 
 41 //    debug();
 42 //    printf("%d %d\n", col, k);
 43 
 44     for(int i=k;i<n;i++)
 45         if(a[i][col])
 46             return -1; // 无解
 47 
 48 //    if(k<m)   //m-k为自由未知量个数
 49 //    {
 50         int stat=1<<(m-k);
 51         int ans=INT_MAX;
 52         for(int i=0;i<stat;i++)
 53         {
 54             int cnt=0;
 55             for(int j=0;j<m-k;j++)
 56                 if(i&(1<<j))
 57                 {
 58                     x[free_x[j]]=1;
 59                     cnt++;
 60                 }
 61                 else
 62                     x[free_x[j]]=0;
 63             for(int j=k-1;j>=0;j--)
 64             {
 65                 int tmp;
 66                 for(tmp=j;tmp<m;tmp++)
 67                     if(a[j][tmp])
 68                         break;
 69                 x[tmp]=a[j][m];
 70                 for(int l=tmp+1;l<m;l++)
 71                     if(a[j][l])
 72                         x[tmp]^=x[l];
 73                 cnt+=x[tmp];
 74             }
 75             if(cnt<ans)
 76                 ans=cnt;
 77         }
 78         return ans;
 79 //    }
 80 
 81 //    //  唯一解 回代
 82 //    for(int i=m-1;i>=0;i--)
 83 //    {
 84 //        x[i]=a[i][m];
 85 //        for(int j=i+1;j<m;j++)
 86 //            x[i]^=(a[i][j] && x[j]);
 87 //    }
 88 //    int ans=0;
 89 //    for(int i=0;i<n*n;i++)
 90 //        ans+=x[i];
 91 //    return ans;
 92 }
 93 
 94 
 95 void init()
 96 {
 97     n=20;
 98     memset(a, 0, sizeof(a));
 99     memset(x, 0, sizeof(x));
100     for(int i=0;i<n;i++)
101     {
102         a[i][i]=1;
103         if(i>0)
104             a[i][i-1]=1;
105         if(i<n-1)
106             a[i][i+1]=1;
107     }
108 }
109 
110 int main()
111 {
112     int X;
113     while(~scanf("%d", &X))
114     {
115         init();
116         a[0][20]=X;
117         for(int i=1;i<n;i++)
118             scanf("%d", &a[i][n]);
119         int t=Gauss(n, n);
120 //        if(t==-1)
121 //        {
122 //            printf("Oh,it's impossible~!!\n");
123 //            continue ;
124 //        }
125         printf("%d\n", t);
126     }
127     return 0;
128 }