首页 > 代码库 > 【POJ】1830 开关问题（高斯消元）
【POJ】1830 开关问题（高斯消元）
http://poj.org/problem?id=1830
高斯消元无解的条件：当存在非法的左式=0而右式不等于0的情况，即为非法。这个可以在消元后，对没有使用过的方程验证是否右式不等于0（此时因为前边消元一定会使得后边的方程左式为0）
高斯消元自由变元：自由变元就是当这些未知量一旦确定，整个方程就确定了。但是这些量是未知的。（例如x+y=5，自由变元就是1，因为无论是x还是y确定，另一个就能唯一确定），而答案要求的是方案，那么显然因为自由变元是可以随便赋值的，而这些值只有2个，开和不开，那么方案数就是2^自由变元。而自由变元的求法很简单，具体解释看白书，其实就是仅当n个不同的方程（就是无论怎么通过其它方程都不会将这两个方程变成一样）才能确定n个解。那么我们如果只确定了x个方程，那么自由变元的数量就是n-x。（这个x可以轻易得到，因为在高斯消元过程中，会消元，而消元会将相同的方程消成这个样子：0=0。那么这个就是没用的方程。
而高斯消元我们要在原有的求一定有解的高斯消元算法改动一下。
我们记录当前的方程x和当前的未知数y，我们知道只有在所有a行，a>=x有A[a][y]!=0时，那么就可以消元，消元后这个方程就是确定的了，那么x++；反之不存在这个a，那么未知数y++
还有一个要注意的是，我们建图时，如果初始状态和末状态相等，意味着这个未知量不需要改变，即A[i][n+1]=0，反之A[i][n+1]=1。且每一个方程组x，如果有未知量y能够造成未知量x改变，那么A[x][y]=1（所以这点千万不要在建图的时候弄错了！）
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=35;typedef int mtx[N][N];int gauss(mtx A, int n) { int x=1, y=1; while(x<=n && y<=n) { int pos=x; while(!A[pos][y] && pos<=n) ++pos; if(A[pos][y]) { for1(i, 1, n+1) swap(A[pos][i], A[x][i]); for1(i, x+1, n) if(A[i][y]) for1(j, y, n+1) A[i][j]^=A[x][j]; ++x; } ++y; } for1(i, x, n) if(A[i][n+1]) return -1; return n-x+1;}int main() { int cs=getint(); mtx a; while(cs--) { CC(a, 0); int n=getint(); for1(i, 1, n) read(a[i][n+1]), a[i][i]=1; for1(i, 1, n) a[i][n+1]^=getint(); int x=getint(), y=getint(); while(x+y) { a[y][x]=1; x=getint(), y=getint(); } int ans=gauss(a, n); if(ans==-1) puts("Oh,it‘s impossible~!!"); else printf("%d\n", 1<<ans); } return 0;}
Description
Input
每组测试数据的格式如下：
第一行 一个数N（0 < N < 29）
第二行 N个0或者1的数，表示开始时N个开关状态。
第三行 N个0或者1的数，表示操作结束后N个开关的状态。
接下来 每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。每组数据以 0 0 结束。
Output
Sample Input
230 0 01 1 11 21 32 12 33 13 20 030 0 01 0 11 22 10 0
Sample Output
4Oh,it‘s impossible~!!
Hint
一共以下四种方法：
操作开关1
操作开关2
操作开关3
操作开关1、2、3 （不记顺序）
Source
【POJ】1830 开关问题（高斯消元）