Gauss消元算法求解开关灯问题

 

 

/*================================================================================================*\

|                                                          Gauss消元算法求解开关灯问题   

\*================================================================================================*/

开关问题:有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与
此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。

对于这类问题,巧妙的运用位运算和gauss算法可以高效的解决。

----------------------------------------------------------------------------------------

开灯问题告诉N(N<=63)盏灯和M(M<=N)个开关,每个开关可以控制K(K<=N)盏灯,给定N盏灯的初始状态S和
要求通过开关控制得到的目标状态E,求可以达到目标状态的方案数。

----------------------------------------------------------------------------------------

简单分析:对于每个开关,有按和不按两种选择(记为0/1); 对于每盏灯有变和不变两种情况(0/1),如果初态和终态不一样
,那么这盏灯是一定要变化的。由此我们就可以得到一个0/1的矩阵:让N盏灯灯作为列向量,开关作为横向量,把每盏灯是否变化
作为第M列(由0开始)这样就得到一个N*(M+1)的矩阵,该矩阵有如下性质:

1. 如果N = M ,那么矩阵为增广矩阵。

2. 该矩阵相当于方程组A * X = B,因此可以求其解。

   1. 若方程组有唯一解,那么,N = M (逆命题:如果M = N ,那么方程组有唯一解 不成立)

   2. 若方程组无实数解,那么,该方程不可以化成严格上三角形式(具体的证明见相关资料,这里不再证明)

   3. 若方程组有多接,即存在自由变元,因为每个自由变元可以取0/1两种情况,那么总共有2^m(m为变元数)解
(也就是不影响最后结果的自由开关的数目)

下面是经过验证的代码:

int getRow(int p, int q, int &row) {

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

             if (!zero(a[i][q])) return a[row=i][q];

      return row=0;

}

void swapRow(int p, int row, int q) {

      for (int k = q; k <= m; k++)

             swap(a[p][k], a[row][k]);

}

i64 gauss() {

      int i = -1, j = -1, k, p, q, ret, row;

      while(++i < n && ++j < m) {

             ret = getRow(i, j, row);

             if (zero(ret)) { i--; continue;}

             if (row != i) swapRow(i, row, j);

             for (p = i+1; p < n; p++) if (a[p][j])

                     for (q = j; q <= m; q++)

                             a[p][q] ^= a[i][q];

      }

      for (k = i; k < n; k++) if(a[k][m]) return -1;

      return (i64)1 << (m-i);

}     //link: hdu3364 http://acm.hdu.edu.cn/showproblem.php?pid=3364

----------------------------------------------------------------------------------------

开关问题:有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,
其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,
果为关就变为开。求: 1. 方案数(自由变元的数目) 2. 给定一个最少的开关方案

----------------------------------------------------------------------------------------

这类问题是上面问题的一种简化:

对于问题一、可以直接套用上面的公式(N=M)

对于问题二、如果构造得到的方程组只有一个解,那么问题解决,这里主要讨论一下多解,
存在自由变元的情况。如果存在自由变元,我们就要枚举每个自由变元(0/1)然后比较选择最小。
枚举时间复杂度为2^m(m为自由变元的个数)

下面是简单的枚举自由元的算法。

int gans(int a[][maxn+1]) {

      int i, j, ret = a[n-1][n];

      for (i = n-2; i >= 0; i--) {

             for (j = i+1; j < n; j++)

                     a[i][n] ^= a[i][j] && a[j][n];

             ret += b[i][n];

      }

      return ret;

}

void dfs(int p, int k) {

      if (p == k) {

             memcpy(b, a, sizeof(b));

             int ret = gans(b);

             if (ret < ans) ans = ret;

             return;

      }

      a[p][n] = 1; dfs(p-1, k);

      a[p][n] = 0; dfs(p-1, k);

}

int gauss() { //……代码见上(n=m)……//

      dfs(n-1, i-1);

      return ans;

}

Link: pku_1222 http://162.105.81.212/JudgeOnline/problem?id=1222

      pku_1681 http://162.105.81.212/JudgeOnline/problem?id=1681

pku_1753 http://162.105.81.212/JudgeOnline/problem?id=1753

pku_1830 http://162.105.81.212/JudgeOnline/problem?id=1830

      pku_3185 http://162.105.81.212/JudgeOnline/problem?id=3185
     hdu_2285 http://acm.hdu.edu.cn/showproblem.php?pid=2285 

 
     

posted on 2010-05-26 17:23 小志 阅读(1513) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案(8)

文章档案(1)

相册

收藏夹

ACM --- Online Judge

小志

最新随笔

积分与排名

最新随笔

最新评论

阅读排行榜

评论排行榜