POJ 3185 The Water Bowls 【一维开关问题高斯消元】

The Water Bowls

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7676		Accepted: 3036

Description

The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing cool water) or upside-down (a position which holds no water). They want all 20 water bowls to be right-side-up and thus use their wide snouts to flip bowls.

Their snouts, though, are so wide that they flip not only one bowl but also the bowls on either side of that bowl (a total of three or -- in the case of either end bowl -- two bowls).

Given the initial state of the bowls (1=undrinkable, 0=drinkable -- it even looks like a bowl), what is the minimum number of bowl flips necessary to turn all the bowls right-side-up?

Input

Line 1: A single line with 20 space-separated integers

Output

Line 1: The minimum number of bowl flips necessary to flip all the bowls right-side-up (i.e., to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the bowls to 20 0's.

Sample Input

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

Sample Output

Hint

Explanation of the sample:

Flip bowls 4, 9, and 11 to make them all drinkable:
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state]
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4]
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]

Source

USACO 2006 January Bronze

题意概括：

N个开关，打开一个开关相邻的开关状态会取反，给一个初始的所有开关状态，要求求出最小的改变开关的次数使得所有开关的状态为关闭；

解题思路：

构造增广矩阵类似于根据开关的关系构造有向图的邻接矩阵；

构造增广矩阵，高斯消元，枚举自由元（二进制枚举状态），寻找最小值；

AC code：

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cmath>
  6 #define INF 0x3f3f3f3f
  7 #define LL long long
  8 using namespace std;
  9 const int MAXN = 300;
 10 int a[MAXN][MAXN];  //增广矩阵
 11 int freeX[MAXN];    //自由元
 12 int x[MAXN];       //解集
 13 int equ, var;
 14 int free_num;
 15 int N;
 16 
 17 int Gauss()
 18 {
 19     int maxRow, col, k;
 20     free_num = 0;
 21     for(k = 0, col = 0; k < equ && col < var; k++, col++){
 22         maxRow = k;
 23         for(int i = k+1; i < equ; i++){
 24             if(abs(a[i][col]) > abs(a[maxRow][col])){
 25                 maxRow = i;
 26             }
 27         }
 28 
 29         if(a[maxRow][col] == 0){
 30             k--;
 31             freeX[free_num++] = col;
 32             continue;
 33         }
 34         if(maxRow != k){
 35             for(int j = col; j < var+1; j++){
 36                 swap(a[k][j], a[maxRow][j]);
 37             }
 38         }
 39 
 40         for(int i = k+1; i < equ; i++){
 41             if(a[i][col] != 0){
 42                 for(int j = col; j < var+1; j++)
 43                     a[i][j] ^= a[k][j];
 44 
 45             }
 46         }
 47     }
 48 
 49     for(int i = k; i < equ; i++)        //无解
 50         if(a[i][col] != 0)  return -1;
 51 
 52     if(k < var) return var-k;           //多解返回自由元个数
 53 
 54     for(int i = var-1; i >= 0; i--){    //唯一解，回代
 55         x[i] = a[i][var];
 56         for(int j = i+1; j < var; j++){
 57             x[i] ^= (a[i][j] && x[j]);
 58         }
 59     }
 60     return 0;
 61 }
 62 
 63 
 64 void solve()
 65 {
 66     int t = Gauss();
 67     if(t == -1){            //无解的情况，其实题目保证有解
 68         printf("inf
");
 69         return;
 70     }
 71     else if(t == 0){                //唯一解
 72         int ans = 0;
 73         for(int i = 0; i < N; i++){
 74             ans += x[i];
 75         }
 76         printf("%d
", ans);
 77         return;
 78     }
 79     else{                              //多解，枚举自由元
 80         int ans = INF;
 81         int tot = (1<<t);
 82         for(int i = 0; i < tot; i++){
 83             int cnt = 0;
 84             for(int j = 0; j < t; j++){
 85                 if(i&(1<<j)){
 86                     x[freeX[j]] = 1;
 87                     cnt++;
 88                 }
 89                 else x[freeX[j]] = 0;
 90             }
 91 
 92             for(int j = var-t-1; j >= 0; j--){
 93                 int index;
 94                 for(index = j; index < var; index++)
 95                     if(a[j][index])
 96                         break;
 97                 x[index] = a[j][var];
 98 
 99                 for(int s = index+1; s < var; s++)
100                     if(a[j][s])
101                         x[index] ^= x[s];
102                 cnt += x[index];
103             }
104             ans = min(ans, cnt);
105         }
106         printf("%d
", ans);
107     }
108     return;
109 }
110 
111 int main()
112 {
113     N = 20;
114     equ = 20;
115     var = 20;
116     memset(a, 0, sizeof(a));
117     memset(x, 0, sizeof(x));
118     for(int i = 0; i < N; i++){
119         a[i][i] = 1;
120         if(i > 0) a[i-1][i] = 1;
121         if(i < N-1) a[i+1][i] = 1;
122     }
123     for(int i = 0; i < N; i++){
124         scanf("%d", &a[i][N]);
125     }
126     solve();
127     return 0;
128 }

View Code