POJ-1830 开关问题高斯消元

POJ-1830 开关问题高斯消元 | 搜索

阅读量：5224 次

发布时间：2019-06-14

本文共 2222 字，大约阅读时间需要 7 分钟。

　　题目链接：

　　Gauss消元真正意义上的第一道（以前做过一道裸的）。。。

　　其实这种题目暴力搜索完全可以解决。。。

　　我们先建立一个矩阵，A[i][j]表示第 i 个开关是否受第 j 个开关的影响，S[i]表示第 i 个开关的初始状态，D[i]表示第 i 个开关的最终状态，X[i]表示操作，那么S*A*X=D，令B=S*D，则有A*X=B：

　　　　A11*X1^A12*X2^......^A1n*Xn=B1

　　　　A21*X1^A22*X2^......^A2n*Xn=B2

　　　　......

　　　　An1*X1^An2*X2^......^Ann*Xn=Bn

　　即求线性方程组的解的个数，那个利用Gauss消元，看最后上三角矩阵中是否存在0 0 0 = 1的情况，则无解，否则求出自由变元的个数cnt，则方法数解为2^cnt。

　　PS：彪哥要我出一道Gauss题目的数据，发现自己高斯消元的题目还没怎么接触过，于是就练练Gauss消元的专题了。

1 //STATUS:C++_AC_16MS_148KB  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 //#include 
        
           6 #include 
         
            7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 #include 
                   
                     17 #include 
                    
                      18 #include 
                     
                       19 #include 
                      
                        20 #include 
                       
                         21 #include 
                        
                          22 #include 
                          23 using namespace std; 24 //using namespace __gnu_cxx; 25 //define 26 #define pii pair
                          
                            27 #define mem(a,b) memset(a,b,sizeof(a)) 28 #define lson l,mid,rt<<1 29 #define rson mid+1,r,rt<<1|1 30 #define PI acos(-1.0) 31 //typedef 32 typedef __int64 LL; 33 typedef unsigned __int64 ULL; 34 //const 35 const int N=33; 36 const int INF=0x3f3f3f3f; 37 //const int MOD=100000,STA=8000010; 38 const LL LNF=1LL<<60; 39 const double EPS=1e-8; 40 const double OO=1e15; 41 const int dx[4]={-1,0,1,0}; 42 const int dy[4]={ 0,1,0,-1}; 43 const int day[13]={ 0,31,28,31,30,31,30,31,31,30,31,30,31}; 44 //Daily Use ... 45 inline int sign(double x){ return (x>EPS)-(x<-EPS);} 46 template
                           
                             T gcd(T a,T b){ return b?gcd(b,a%b):a;} 47 template
                            
                              T lcm(T a,T b){ return a/gcd(a,b)*b;} 48 template
                             
                               inline T lcm(T a,T b,T d){ return a/d*b;} 49 template
                              
                                inline T Min(T a,T b){ return a
                               
                                 inline T Max(T a,T b){ return a>b?a:b;} 51 template
                                
                                  inline T Min(T a,T b,T c){ return min(min(a, b),c);} 52 template
                                 
                                   inline T Max(T a,T b,T c){ return max(max(a, b),c);} 53 template
                                  
                                    inline T Min(T a,T b,T c,T d){ return min(min(a, b),min(c,d));} 54 template
                                   
                                     inline T Max(T a,T b,T c,T d){ return max(max(a, b),max(c,d));} 55 //End 56 57 int A[N][N]; 58 int T,n; 59 60 int gauss(int n) 61 { 62 int i,j,k,cnt,ok; 63 for(i=0;i
                                    
                                     =0;i--){ 80 ok=1; 81 for(j=i;j

转载于:https://www.cnblogs.com/zhsl/archive/2013/05/24/3096644.html

你可能感兴趣的文章