首页 > 代码库 > poj 1830 开关问题 (高斯消元)

poj 1830 开关问题 (高斯消元)

2024-07-18 04:51:55   219人阅读

题目链接

题意：给定N(N < 29)个开关，每个开关打开和关闭的时候会引起另外一个开关的变化，本来为打开的会变成关闭，

本来关闭的会变成打开。给定N个开关的初始状态和终止状态，以及关联的开关关系，求共有多少种方案从初始状态变成终止状态（不计顺序，并且每个开关只能操作至多一次）。

分析：

由于开关只有打开和关闭两种状态，所以对于每个开关的打开和关闭，组合一下总共有2^N种情况，枚举所有情况判可行性，对于这个数据量来说是不现实的，需要想办法优化。

start + x(i) * A(i) = end

x(i) * A(i) = start ^ end 即当开始状态和结束状态不同的时候才取1 来改变状态。。

系数矩阵A[i][j]代表了开关之间的连带关系:

1) 如果第j个开关的操作能够影响第i个开关的状态，那么A[i][j] = 1;

2) 如果第j个开关的操作不影响第i个开关的状态，那么A[i][j] = 0;

3) 特殊的A[i][i] = 1(开关本身的操作必然会影响自己的当前状态);

但是还是不理解为什么不是前面 影响 后面？？？？

 

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <cmath>  6 #include <algorithm>  7 #define LL __int64  8 const int maxn = 30+10;  9 using namespace std; 10 int equ, var, fn; 11 int a[maxn][maxn], x[maxn]; 12  13 int gcd(int a, int b) 14 { 15     return b==0?a:gcd(b, a%b); 16 } 17 int lcm(int a, int b) 18 { 19     return a*b/gcd(a, b); 20 } 21 int Gauss() 22 { 23     int x_mo; 24     x_mo = 2; 25     int i, j, k, max_r, col; 26     int ta, tb, LCM; 27     col = 0; 28  29     for(k = 0; k<equ && col<var; k++, col++) 30     { 31         max_r = k; 32         for(i = k+1; i < equ; i++) 33             if(abs(a[i][col])>abs(a[max_r][col])) 34             max_r = i; 35  36         if(max_r != k) 37             for(j = k; j < var+1; j++) 38             swap(a[k][j], a[max_r][j]); 39  40         if(a[k][col]==0) 41         { 42             k--; 43             continue; 44         } 45         for(i = k+1; i < equ; i++) 46         { 47             if(a[i][col] != 0) 48             { 49                 LCM = lcm(abs(a[i][col]), abs(a[k][col])); 50                 ta = LCM/abs(a[i][col]); 51                 tb= LCM/abs(a[k][col]); 52                 if(a[i][col]*a[k][col] < 0) tb = -tb; 53  54                 for(j = col; j < var+1; j++) 55                 a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%x_mo+x_mo)%x_mo; 56             } 57         } 58     } 59     for(i = k; i < equ; i++) 60     if(a[i][col] != 0) 61     return -1; 62  63     if(k < var) 64         return var-k; 65     return 0; 66 } 67 int main() 68 { 69     int i, t, n; 70     int b[maxn], e[maxn], c, d; 71     scanf("%d", &t); 72     while(t--) 73     { 74         cin>>n; 75         equ = n; 76         var = n; 77         memset(a, 0, sizeof(a)); 78         for(i = 0; i < n; i++) 79         cin>>b[i]; 80         for(i = 0; i < n; i++) 81         cin>>e[i]; 82         while(cin>>c>>d) 83         { 84             if(c==0 && d==0) break; 85             a[d-1][c-1] = 1; //注意题目里是从1开始的，注意是c在后，后面影响前面。但是还是不理解为什么 86         } 87         for(i = 0; i < n; i++) 88             a[i][i] = 1; 89         for(i = 0; i < n; i++) 90         a[i][n] = (b[i]^e[i]); //当开始状态和结束状态不同的时候才取1 来改变状态 91         fn = Gauss(); 92         if(fn==-1) 93         printf("Oh,it‘s impossible~!!\n"); 94         else 95         { 96             fn = (1<<fn); //因为有fn个变元，而有0，1两种状态，所以情况数是2^fn。 97             cout<<fn<<endl; 98         } 99     }100     return 0;101 }

 


联系
我们