高斯消元

高斯消元求线性方程组的解 高斯消元复杂度 O(N^3) 参考 ：整数线性方程组的解 | 自由变元的个数 http://www.cnblogs.com/kuangbin/archive/2012/09/01/2667044.html 浮点线性方程组的解 http://www.cnblogs.com/kuangbin/p/3428573.html 异或方程组的解 http://blog.csdn.net/u012936765/article/details/46966517 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<set> #include<map> using namespace std ; const int maxn = 300 ; int equ , var ; int a[maxn][maxn] ; int x[maxn] ; int free_x[maxn] ; int free_num ; //高斯消元枚举自由变元，如果自由变元为0 个，那么得到解，否则枚举自由变元 //一类开关问题：高斯消元求异或方程组的解 void dis(){ for(int i = 0 ;i<10 ;i++){ for( int j = 0 ;j<10 ;j++) cout<<a[i][j]<<" "; cout<<endl; } cout<<"asdfasd"<<endl; for(int i = 0 ;i<10 ;i++) cout<<x[i]<<" "; cout<<endl; } int Gauss(){ int max_r , col , k ; free_num = 0 ; for( k = 0 , col = 0 ; k < equ && col < var ; k ++ , col ++){ max_r = k ; //找最大的行 for( int i = k + 1 ; i<equ ;i++){ if( abs( a[i][col] > abs( a[max_r][col] ))) max_r = i ; } //自由变元 if( a[max_r][col] == 0 ){ k -- ; free_x[ free_num ++ ] = col ; continue ; } //交换两行 if( max_r != k ){ for( int j = col ; j<var + 1 ; j++){ swap( a[k][j] , a[max_r][j]) ; } } for(int i = k + 1 ; i<equ ;i++){ if( a[i][col] != 0 ){ for( int j = col ; j< var + 1 ; j++) a[i][j] ^= a[k][j] ; } } } for(int i = k ;i<equ ;i++) if( a[i][col] != 0 ) return -1 ; if( k < var) return var - k ; for( int i = var - 1 ; i>=0 ;i--){ x[i] = a[i][var] ; for( int j = i + 1 ; j<var ; j++) x[i] ^= ( a[i][j] && x[j] ) ; } dis() ; return 0 ; } int n ; void init(){ memset( a, 0 , sizeof( a )) ; memset( x , 0 , sizeof( x )) ; equ = n* n ; var = n* n ; for( int i = 0 ; i < n ; i++) for( int j = 0 ; j< n ;j++){ int t = i * n + j ; a[t][t] = 1 ; if( i>0 ) a[ ( i - 1 ) * n + j ][t] = 1 ; if( i<n-1 ) a[ ( i+1) * n + j ][t] = 1; if( j > 0 ) a[i*n + j -1][t] = 1 ; if( j < n - 1) a[i* n + j + 1][t] = 1 ; } } void solve(){ int t = Gauss() ; cout<<t<<endl; if( t== -1 ){ printf("inf\n") ; return ; } else if( t== 0 ){ int ans = 0 ; for( int i = 0 ; i<n* n ;i++){ ans += x[i] ; } printf("%d\n" , ans ) ; return ; } else{ int ans = 0x3f3f3f3f ; int tot = ( 1<< t ) ; for( int i = 0 ; i< tot ; i++){ int cnt = 0 ; for( int j = 0 ; j<t ; j++){ if( i & ( 1<< j )){ x[free_x[j]] = 1 ; cnt ++ ; } else x[free_x[j]] = 0 ; } for( int j = var - t - 1 ; j >= 0 ; j--){ int idx ; for( idx = j ; idx < var ; idx ++) if( a[j][idx]) break ; x[idx] = a[j][var] ; for( int l = idx + 1 ; l < var ; l++) if( a[j][l] ) x[idx] ^= x[l] ; cnt += x[idx] ; } ans = min( ans , cnt ) ; } printf("%d\n" , ans ) ; } } char str[30][30] ; int main(){ int T ; scanf("%d" , &T) ; while( T-- ){ scanf("%d" , & n ) ; init() ; for( int i = 0 ; i< n ;i++){ scanf("%s" , str[i]) ; for( int j = 0 ; j< n ;j ++){ if( str[i][j] == 'y') a[i* n + j ][n* n ] = 0 ; else a[i*n+j][n*n ] = 1 ; } } solve() ; } return 0 ; } #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<math.h> using namespace std; const int MAXN=400; int a[MAXN][MAXN];//增广矩阵 int x[MAXN];//解集 bool free_x[MAXN];//标记是否是不确定的变元 //高斯消元求模线性方程组的解 inline int gcd(int a,int b) { int t; while(b!=0) { t=b; b=a%b; a=t; } return a; } inline int lcm(int a,int b) { return a/gcd(a,b)*b;//先除后乘防溢出 } // 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解， //-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数) //有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var. int Gauss(int equ,int var) { int i,j,k; int max_r;// 当前这列绝对值最大的行. int col;//当前处理的列 int ta,tb; int LCM; int temp; int free_x_num; int free_index; for(int i=0;i<=var;i++) { x[i]=0; free_x[i]=true; } //转换为阶梯阵. col=0; // 当前处理的列 for(k = 0;k < equ && col < var;k++,col++) {// 枚举当前处理的行. // 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差) max_r=k; for(i=k+1;i<equ;i++) { if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; } if(max_r!=k) {// 与第k行交换. for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]); } if(a[k][col]==0) {// 说明该col列第k行以下全是0了，则处理当前行的下一列. k--; continue; } for(i=k+1;i<equ;i++) {// 枚举要删去的行. if(a[i][col]!=0) { LCM = lcm(abs(a[i][col]),abs(a[k][col])); ta = LCM/abs(a[i][col]); tb = LCM/abs(a[k][col]); if(a[i][col]*a[k][col]<0)tb=-tb;//异号的情况是相加 for(j=col;j<var+1;j++) { a[i][j] = ((a[i][j]*ta-a[k][j]*tb)%7+7)%7; } } } } // 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0). for (i = k; i < equ; i++) { // 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换. if ( a[i][col] != 0) return -1; } // 2. 无穷解的情况: 在var * (var + 1)的增广阵中出现(0, 0, ..., 0)这样的行，即说明没有形成严格的上三角阵. // 且出现的行数即为自由变元的个数. if (k < var) { // 首先，自由变元有var - k个，即不确定的变元至少有var - k个. for (i = k - 1; i >= 0; i--) { // 第i行一定不会是(0, 0, ..., 0)的情况，因为这样的行是在第k行到第equ行. // 同样，第i行一定不会是(0, 0, ..., a), a != 0的情况，这样的无解的. free_x_num = 0; // 用于判断该行中的不确定的变元的个数，如果超过1个，则无法求解，它们仍然为不确定的变元. for (j = 0; j < var; j++) { if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j; } if (free_x_num > 1) continue; // 无法求解出确定的变元. // 说明就只有一个不确定的变元free_index，那么可以求解出该变元，且该变元是确定的. temp = a[i][var]; for (j = 0; j < var; j++) { if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j]%7; temp=(temp%7+7)%7; } x[free_index] = (temp / a[i][free_index])%7; // 求出该变元. free_x[free_index] = 0; // 该变元是确定的. } return var - k; // 自由变元有var - k个. } // 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵. // 计算出Xn-1, Xn-2 ... X0. for (i = var - 1; i >= 0; i--) { temp = a[i][var]; for (j = i + 1; j < var; j++) { if (a[i][j] != 0) temp -= a[i][j] * x[j]; temp=(temp%7+7)%7; } while (temp % a[i][i] != 0) temp+=7; x[i] =( temp / a[i][i])%7 ; } return 0; } int tran(char *s) { if(strcmp(s,"MON")==0)return 1; else if(strcmp(s,"TUE")==0) return 2; else if(strcmp(s,"WED")==0) return 3; else if(strcmp(s,"THU")==0) return 4; else if(strcmp(s,"FRI")==0) return 5; else if(strcmp(s,"SAT")==0) return 6; else return 7; } char str1[20]; char str2[20]; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n,m; int k; int t; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; memset(a,0,sizeof(a)); for(int i=0;i<m;i++) { scanf("%d%s%s",&k,&str1,&str2); a[i][n]=((tran(str2)-tran(str1)+1)%7+7)%7;//这里减的顺序很重要，取了绝对值就WA了。 while(k--) { scanf("%d",&t); t--; a[i][t]++; a[i][t]%=7; } } int ans=Gauss(m,n); if(ans==0) { for(int i=0;i<n;i++) if(x[i]<=2)x[i]+=7;//注意看题意 for(int i=0;i<n-1;i++)printf("%d ",x[i]); printf("%d\n",x[n-1]); } else if(ans==-1)printf("Inconsistent data.\n"); else printf("Multiple solutions.\n"); } return 0; }