POJ 1222 POJ 1830 POJ 1681 POJ 1753 POJ 3185 高斯消元求解一类开关问题

这几个题目都类似，都可以使用高斯消元来求解一个模2的01方程组来解决。

有时候需要枚举*变元，有的是判断存不存在解

普通的问题。

肯定有唯一解。肯定枚举第一行去做，也可以使用高斯消元。

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013/8/17 18:25:42

 File Name     :F:\2013ACM练习\专题学习\高斯消元\POJ1222.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 //对2取模的01方程组

 const int MAXN = ;

 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var

 int equ,var;

 int a[MAXN][MAXN]; //增广矩阵

 int x[MAXN]; //解集

 int free_x[MAXN];//用来存储*变元（多解枚举*变元可以使用）

 int free_num;//*变元的个数

 //返回值为-1表示无解，为0是唯一解，否则返回*变元个数

 int Gauss()

 {

     int max_r,col,k;

     free_num = ;

     for(k = , col =  ; k < equ && col < var ; k++, col++)

     {

         max_r = k;

         for(int i = k+;i < equ;i++)

         {

             if(abs(a[i][col]) > abs(a[max_r][col]))

                 max_r = i;

         }

         if(a[max_r][col] == )

         {

             k--;

             free_x[free_num++] = col;//这个是*变元

             continue;

         }

         if(max_r != k)

         {

             for(int j = col; j < var+; j++)

                 swap(a[k][j],a[max_r][j]);

         }

         for(int i = k+;i < equ;i++)

         {

             if(a[i][col] != )

             {

                 for(int j = col;j < var+;j++)

                     a[i][j] ^= a[k][j];

             }

         }

     }

     for(int i = k;i < equ;i++)

         if(a[i][col] != )

             return -;//无解

     if(k < var) return var-k;//*变元个数

     //唯一解，回代

     for(int i = var-; i >= ;i--)

     {

         x[i] = a[i][var];

         for(int j = i+;j < var;j++)

             x[i] ^= (a[i][j] && x[j]);

     }

     return ;

 }

 void init()

 {

     memset(a,,sizeof(a));

     memset(x,,sizeof(x));

     equ = ;

     var = ;

     for(int i = ;i < ;i++)

         for(int j = ;j < ;j++)

         {

             int t = i*+j;

             a[t][t] = ;

             if(i > )a[(i-)*+j][t] = ;

             if(i < )a[(i+)*+j][t] = ;

             if(j > )a[i*+j-][t] = ;

             if(j < )a[i*+j+][t] = ;

         }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T;

     int iCase = ;

     scanf("%d",&T);

     while(T--)

     {

         iCase++;

         init();

         for(int i = ;i < ;i++)

             scanf("%d",&a[i][]);

         Gauss();

         printf("PUZZLE #%d\n",iCase);

         for(int i = ;i < ;i++)

         {

             for(int j = ;j < ;j++)

                 printf("%d ",x[i*+j]);

             printf("%d\n",x[i*+]);

         }

     }

     return ;

 }

POJ 1830 开关问题

输出方案数，就是求出有多少个*变元就可以了。

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013/8/17 19:44:33

 File Name     :F:\2013ACM练习\专题学习\高斯消元\POJ1830.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 //对2取模的01方程组

 const int MAXN = ;

 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var

 int equ,var;

 int a[MAXN][MAXN]; //增广矩阵

 int x[MAXN]; //解集

 int free_x[MAXN];//用来存储*变元（多解枚举*变元可以使用）

 int free_num;//*变元的个数

 //返回值为-1表示无解，为0是唯一解，否则返回*变元个数

 int Gauss()

 {

     int max_r,col,k;

     free_num = ;

     for(k = , col =  ; k < equ && col < var ; k++, col++)

     {

         max_r = k;

         for(int i = k+;i < equ;i++)

         {

             if(abs(a[i][col]) > abs(a[max_r][col]))

                 max_r = i;

         }

         if(a[max_r][col] == )

         {

             k--;

             free_x[free_num++] = col;//这个是*变元

             continue;

         }

         if(max_r != k)

         {

             for(int j = col; j < var+; j++)

                 swap(a[k][j],a[max_r][j]);

         }

         for(int i = k+;i < equ;i++)

         {

             if(a[i][col] != )

             {

                 for(int j = col;j < var+;j++)

                     a[i][j] ^= a[k][j];

             }

         }

     }

     for(int i = k;i < equ;i++)

         if(a[i][col] != )

             return -;//无解

     if(k < var) return var-k;//*变元个数

     //唯一解，回代

     for(int i = var-; i >= ;i--)

     {

         x[i] = a[i][var];

         for(int j = i+;j < var;j++)

             x[i] ^= (a[i][j] && x[j]);

     }

     return ;

 }

 void init()

 {

     memset(a,,sizeof(a));

     memset(x,,sizeof(x));

 }

 int start[MAXN],end[MAXN];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int n;

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i = ;i < n;i++)

             scanf("%d",&start[i]);

         for(int i = ;i < n;i++)

             scanf("%d",&end[i]);

         init();

         equ = var = n;

         for(int i = ;i < n;i++)

             a[i][i] = ;

         int u,v;

         while(scanf("%d%d",&u,&v) == )

         {

             if(u ==  && v == )break;

             a[v-][u-] = ;

         }

         for(int i = ;i < n;i++)

             a[i][n] = (start[i]^end[i]);

         int ans = Gauss();

         if(ans == -)

             printf("Oh,it's impossible~!!\n");

         else printf("%d\n",(<<ans));

     }

     return ;

 }

POJ 1681 Painter's Problem

需要步数最少的，要枚举*变元求解。

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013/8/17 19:56:07

 File Name     :F:\2013ACM练习\专题学习\高斯消元\POJ1681.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 //对2取模的01方程组

 const int MAXN = ;

 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var

 int equ,var;

 int a[MAXN][MAXN]; //增广矩阵

 int x[MAXN]; //解集

 int free_x[MAXN];//用来存储*变元（多解枚举*变元可以使用）

 int free_num;//*变元的个数

 //返回值为-1表示无解，为0是唯一解，否则返回*变元个数

 int Gauss()

 {

     int max_r,col,k;

     free_num = ;

     for(k = , col =  ; k < equ && col < var ; k++, col++)

     {

         max_r = k;

         for(int i = k+;i < equ;i++)

         {

             if(abs(a[i][col]) > abs(a[max_r][col]))

                 max_r = i;

         }

         if(a[max_r][col] == )

         {

             k--;

             free_x[free_num++] = col;//这个是*变元

             continue;

         }

         if(max_r != k)

         {

             for(int j = col; j < var+; j++)

                 swap(a[k][j],a[max_r][j]);

         }

         for(int i = k+;i < equ;i++)

         {

             if(a[i][col] != )

             {

                 for(int j = col;j < var+;j++)

                     a[i][j] ^= a[k][j];

             }

         }

     }

     for(int i = k;i < equ;i++)

         if(a[i][col] != )

             return -;//无解

     if(k < var) return var-k;//*变元个数

     //唯一解，回代

     for(int i = var-; i >= ;i--)

     {

         x[i] = a[i][var];

         for(int j = i+;j < var;j++)

             x[i] ^= (a[i][j] && x[j]);

     }

     return ;

 }

 int n;

 void init()

 {

     memset(a,,sizeof(a));

     memset(x,,sizeof(x));

     equ = n*n;

     var = n*n;

     for(int i = ;i < n;i++)

         for(int j = ;j < n;j++)

         {

             int t = i*n+j;

             a[t][t] = ;

             if(i > )a[(i-)*n+j][t] = ;

             if(i < n-)a[(i+)*n+j][t] = ;

             if(j > )a[i*n+j-][t] = ;

             if(j < n-)a[i*n+j+][t] = ;

         }

 }

 void solve()

 {

     int t = Gauss();

     if(t == -)

     {

         printf("inf\n");

         return;

     }

     else if(t == )

     {

         int ans = ;

         for(int i = ;i < n*n;i++)

             ans += x[i];

         printf("%d\n",ans);

         return;

     }

     else

     {

         //枚举*变元

         int ans = 0x3f3f3f3f;

         int tot = (<<t);

         for(int i = ;i < tot;i++)

         {

             int cnt = ;

             for(int j = ;j < t;j++)

             {

                 if(i&(<<j))

                 {

                     x[free_x[j]] = ;

                     cnt++;

                 }

                 else x[free_x[j]] = ;

             }

             for(int j = var-t-;j >= ;j--)

             {

                 int idx;

                 for(idx = j;idx < var;idx++)

                     if(a[j][idx])

                         break;

                 x[idx] = a[j][var];

                 for(int l = idx+;l < var;l++)

                     if(a[j][l])

                         x[idx] ^= x[l];

                 cnt += x[idx];

             }

             ans = min(ans,cnt);

         }

         printf("%d\n",ans);

     }

 }

 char str[][];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         init();

         for(int i = ;i < n;i++)

         {

             scanf("%s",str[i]);

             for(int j = ;j < n;j++)

             {

                 if(str[i][j] == 'y')

                     a[i*n+j][n*n] = ;

                 else a[i*n+j][n*n] = ;

             }

         }

         solve();

     }

     return ;

 }

POJ 1753 Flip Game

数据范围很小，随便搞，也是要枚举*变元。。。。这题用高斯消元真是杀鸡用牛刀了

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013/8/17 20:53:13

 File Name     :F:\2013ACM练习\专题学习\高斯消元\POJ1753.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 //对2取模的01方程组

 const int MAXN = ;

 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var

 int equ,var;

 int a[MAXN][MAXN]; //增广矩阵

 int x[MAXN]; //解集

 int free_x[MAXN];//用来存储*变元（多解枚举*变元可以使用）

 int free_num;//*变元的个数

 //返回值为-1表示无解，为0是唯一解，否则返回*变元个数

 int Gauss()

 {

     int max_r,col,k;

     free_num = ;

     for(k = , col =  ; k < equ && col < var ; k++, col++)

     {

         max_r = k;

         for(int i = k+;i < equ;i++)

         {

             if(abs(a[i][col]) > abs(a[max_r][col]))

                 max_r = i;

         }

         if(a[max_r][col] == )

         {

             k--;

             free_x[free_num++] = col;//这个是*变元

             continue;

         }

         if(max_r != k)

         {

             for(int j = col; j < var+; j++)

                 swap(a[k][j],a[max_r][j]);

         }

         for(int i = k+;i < equ;i++)

         {

             if(a[i][col] != )

             {

                 for(int j = col;j < var+;j++)

                     a[i][j] ^= a[k][j];

             }

         }

     }

     for(int i = k;i < equ;i++)

         if(a[i][col] != )

             return -;//无解

     if(k < var) return var-k;//*变元个数

     //唯一解，回代

     for(int i = var-; i >= ;i--)

     {

         x[i] = a[i][var];

         for(int j = i+;j < var;j++)

             x[i] ^= (a[i][j] && x[j]);

     }

     return ;

 }

 int n;

 void init()

 {

     memset(a,,sizeof(a));

     memset(x,,sizeof(x));

     equ = n*n;

     var = n*n;

     for(int i = ;i < n;i++)

         for(int j = ;j < n;j++)

         {

             int t = i*n+j;

             a[t][t] = ;

             if(i > )a[(i-)*n+j][t] = ;

             if(i < n-)a[(i+)*n+j][t] = ;

             if(j > )a[i*n+j-][t] = ;

             if(j < n-)a[i*n+j+][t] = ;

         }

 }

 const int INF = 0x3f3f3f3f;

 int solve()

 {

     int t = Gauss();

     if(t == -)

     {

         return INF;

     }

     else if(t == )

     {

         int ans = ;

         for(int i = ;i < n*n;i++)

             ans += x[i];

         return ans;

     }

     else

     {

         //枚举*变元

         int ans = INF;

         int tot = (<<t);

         for(int i = ;i < tot;i++)

         {

             int cnt = ;

             for(int j = ;j < t;j++)

             {

                 if(i&(<<j))

                 {

                     x[free_x[j]] = ;

                     cnt++;

                 }

                 else x[free_x[j]] = ;

             }

             for(int j = var-t-;j >= ;j--)

             {

                 int idx;

                 for(idx = j;idx < var;idx++)

                     if(a[j][idx])

                         break;

                 x[idx] = a[j][var];

                 for(int l = idx+;l < var;l++)

                     if(a[j][l])

                         x[idx] ^= x[l];

                 cnt += x[idx];

             }

             ans = min(ans,cnt);

         }

         return ans;

     }

 }

 char str[][];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     n = ;

     for(int i = ;i < ;i++)

         scanf("%s",str[i]);

     init();

     for(int i = ;i < ;i++)

         for(int j = ;j < ;j++)

         {

             if(str[i][j] == 'b')a[i*+j][] = ;

             else a[i*+j][] = ;

         }

     int ans1 = solve();

     init();

     for(int i = ;i < ;i++)

         for(int j = ;j < ;j++)

         {

             if(str[i][j] == 'b')a[i*+j][] = ;

             else a[i*+j][] = ;

         }

     int ans2 = solve();

     if(ans1 == INF && ans2 == INF)

         printf("Impossible\n");

     else printf("%d\n",min(ans1,ans2));

     return ;

 }

POJ 3185 The Water Bowls

一维的了，更简单的还是枚举比较好。

高斯消元随便搞

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013/8/17 21:53:09

 File Name     :F:\2013ACM练习\专题学习\高斯消元\POJ3185.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 //对2取模的01方程组

 const int MAXN = ;

 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var

 int equ,var;

 int a[MAXN][MAXN]; //增广矩阵

 int x[MAXN]; //解集

 int free_x[MAXN];//用来存储*变元（多解枚举*变元可以使用）

 int free_num;//*变元的个数

 //返回值为-1表示无解，为0是唯一解，否则返回*变元个数

 int Gauss()

 {

     int max_r,col,k;

     free_num = ;

     for(k = , col =  ; k < equ && col < var ; k++, col++)

     {

         max_r = k;

         for(int i = k+;i < equ;i++)

         {

             if(abs(a[i][col]) > abs(a[max_r][col]))

                 max_r = i;

         }

         if(a[max_r][col] == )

         {

             k--;

             free_x[free_num++] = col;//这个是*变元

             continue;

         }

         if(max_r != k)

         {

             for(int j = col; j < var+; j++)

                 swap(a[k][j],a[max_r][j]);

         }

         for(int i = k+;i < equ;i++)

         {

             if(a[i][col] != )

             {

                 for(int j = col;j < var+;j++)

                     a[i][j] ^= a[k][j];

             }

         }

     }

     for(int i = k;i < equ;i++)

         if(a[i][col] != )

             return -;//无解

     if(k < var) return var-k;//*变元个数

     //唯一解，回代

     for(int i = var-; i >= ;i--)

     {

         x[i] = a[i][var];

         for(int j = i+;j < var;j++)

             x[i] ^= (a[i][j] && x[j]);

     }

     return ;

 }

 void init()

 {

     memset(a,,sizeof(a));

     memset(x,,sizeof(x));

     equ = ;

     var = ;

     for(int i = ;i < ;i++)

     {

         a[i][i] = ;

         if(i > ) a[i-][i] = ;

         if(i < )a[i+][i] = ;

     }

 }

 void solve()

 {

     int t = Gauss();

     if(t == -)

     {

         printf("inf\n");

         return;

     }

     else if(t == )

     {

         int ans = ;

         for(int i = ;i < ;i++)

             ans += x[i];

         printf("%d\n",ans);

         return;

     }

     else

     {

         //枚举*变元

         int ans = 0x3f3f3f3f;

         int tot = (<<t);

         for(int i = ;i < tot;i++)

         {

             int cnt = ;

             for(int j = ;j < t;j++)

             {

                 if(i&(<<j))

                 {

                     x[free_x[j]] = ;

                     cnt++;

                 }

                 else x[free_x[j]] = ;

             }

             for(int j = var-t-;j >= ;j--)

             {

                 int idx;

                 for(idx = j;idx < var;idx++)

                     if(a[j][idx])

                         break;

                 x[idx] = a[j][var];

                 for(int l = idx+;l < var;l++)

                     if(a[j][l])

                         x[idx] ^= x[l];

                 cnt += x[idx];

             }

             ans = min(ans,cnt);

         }

         printf("%d\n",ans);

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     init();

     for(int i = ;i < ;i++)

         scanf("%d",&a[i][]);

     solve();

     return ;

 }

专题：

高斯消元解方程：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29538#overview

秒客网

POJ 1222 POJ 1830 POJ 1681 POJ 1753 POJ 3185 高斯消元求解一类开关问题

相关文章