高斯消元專題

由於老師的講課，我又重拾高斯消元，做了一天的高斯，感覺老師講得很好，模板也不錯，我懶得自己寫，就把同僚的模板拿過來用了，反正基本原理都懂了。
 高斯消元模板題，只有唯一解。
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
 
using namespace std; 
const int maxn=30; 
int a[maxn][maxn+1],x[maxn]; 
int equ,var,free_num; 
void Debug() 
{ 
   for(int i=0;i<equ;i++) 
   { 
      for(int j=0;j<var+1;j++) 
        cout<<a[i][j]<<" "; 
      cout<<endl; 
   } 
} 
int gcd(int a,int b) 
{ 
     if(a<0) return gcd(-a,b); 
     if(b<0) return gcd(a,-b); 
     return b==0?a:gcd(b,a%b); 
} 
int Gauss() 
{ 
    int k,col=0; 
    for(k=0;k<equ&&col<var;k++,col++) 
    { 
        int mx=k; 
        for(int i=k+1;i<equ;i++) 
          if(a[i][col]>a[mx][col]) mx=i; 
        if(mx!=k) 
           for(int i=k;i<var+1;i++)  swap(a[k][i],a[mx][i]); 
        if(!a[k][col]) { k--;continue; } 
        for(int i=k+1;i<equ;i++) 
           if(a[i][col]!=0) 
           { 
               int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col]; 
               int ta=lcm/a[i][col],tb=lcm/a[k][col]; 
               if(a[i][col]*a[k][col] < 0)  tb = -tb; 
               for(int j=col;j<var+1;j++) 
                 a[i][j]=((a[i][j]*ta)%2 - (a[k][j]*tb)%2+2)%2; 
           } 
     } 
    // Debug(); 
     //cout<<col<<endl<<endl; 
     for(int i=k;i<equ;i++) 
        if(a[i][var]) return -1; 
     for(int i=0,j;i<equ;i++) 
         if(!a[i][i]) 
         { 
              for(j=i+1;j<var;j++) 
                 if(a[i][j]) break; 
              if(j>=var) break; 
              for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); 
         } 
 
         //唯一解 
      for(int i=k-1;i>=0;i--) 
      { 
          int tmp=a[i][var]%2; 
          for(int j=i+1;j<var+1;j++) 
             if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%2+2)%2; 
          x[i]=(tmp/a[i][i])%2; 
      } 
} 
void init() 
{ 
     memset(a,0,sizeof(a)); 
     memset(x,0,sizeof(x)); 
     for(int i=0;i<5;i++) 
     for(int j=0;j<6;j++) 
      { 
           if(i!=0) a[i*6+j][(i-1)*6+j]=1; 
           if(i!=4) a[i*6+j][(i+1)*6+j]=1; 
           if(j!=0) a[i*6+j][i*6+j-1]=1; 
           if(j!=5) a[i*6+j][i*6+j+1]=1; 
           a[i*6+j][i*6+j]=1; 
      } 
} 
int main(int argc, char *argv[]) 
{ 
    int T,ca=1; 
    scanf("%d",&T); 
    equ=30,var=30; 
    while(T--) 
    { 
        init(); 
        for(int i=0;i<30;i++) scanf("%d",&a[i][30]); 
        Gauss(); 
        printf("PUZZLE #%d\n",ca++); 
        for(int i=0;i<30;i++) 
        { 
            if(i%6!=0) putchar(' '); 
            printf("%d",x[i]); 
            if(i%6==5) puts(""); 
        } 
    } 
    return EXIT_SUCCESS; 
} 

 動最少的磚，枚舉自由元，找1的個數最少的那組解。
[cpp]
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <stdio.h> 
using namespace std; 
const int inf=0x3fffffff; 
 
const int maxn=15*15; 
int a[maxn][maxn+1],x[maxn],equ,var,n; 
 char s[20][20]; 
 
void init() 
{ 
    equ=var=n*n; 
    for(int i=0;i<n;i++) 
       scanf("%s",s[i]); 
    memset(a,0,sizeof(a)); 
    for(int i=0;i<var;i++) a[i][var]= (s[i/n][i%n]!='y'),a[i][i]=1; 
    for(int i=0;i<n;i++) 
    for(int j=0;j<n;j++) 
    { 
       /* if(i!=0) a[(i-1)*n+j][i*n+j]=1;
        if(i!=n-1) a[(i+1)*n+j][i*n+j]=1;
        if(j!=0) a[i*n+j-1][i*n+j]=1;
        if(j!=n-1) a[i*n+j+1][i*n+j]=1;*/ 
             if(i-1>=0) a[i*n+j][(i-1)*n+j]=1; 
             if(i+1<n) a[i*n+j][(i+1)*n+j]=1; 
             if(j-1>=0) a[i*n+j][i*n+j-1]=1; 
             if(j+1<n) a[i*n+j][i*n+j+1]=1; 
    } 
} 
void debug() 
{ 
    for(int i=0;i<equ;i++) 
    { 
        for(int j=0;j<=var;j++) 
          cout<<a[i][j]<<" "; 
        cout<<endl; 
    } 
    cout<<endl; 
} 
int gcd(int a,int b) 
{ 
    if(a<0) return gcd(-a,b); 
    if(b<0) return gcd(a,-b); 
    return b==0?a:gcd(b,a%b); 
} 
 
int gauss() 
{ 
    int k,col; 
    for(k=col=0;k<equ&&col<var;k++,col++) 
    { 
        int mx=k; 
        for(int i=k+1;i<equ;i++) 
           if(a[i][col]>a[mx][col]) mx=i; 
        if(k!=mx){ 
            for(int i=k;i<var+1;i++) 
               swap(a[k][i],a[mx][i]); 
        } 
        if(!a[k][col]){ 
            k--;continue; 
        } 
        for(int i=k+1;i<equ;i++) 
        if(a[i][col]) 
        { 
            int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col]; 
            int ta=lcm/a[i][col],tb=lcm/a[k][col]; 
            for(int j=col;j<var+1;j++) 
               a[i][j]=((a[i][j]*ta-a[k][j]*tb)%2+2)%2; 
        } 
    } 
   // debug(); 
    for(int i=k;i<equ;i++) 
      if(a[i][col]) return inf; 
 
    for(int i=0,j;i<equ;i++) 
       if(!a[i][i]) 
       { 
           for(j=i+1;j<var;j++) 
             if(a[i][j]) break; 
           if(j>=var) break; 
           for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); 
       } 
 
 /*   int ret=inf,lim= (1<<(var-k));
 
   for(int j=0;j<lim;j++)
   {
     for(int i=0;i<(var-k);i++)
       if(j&(1<<i)) x[equ-1-i]=1;
       else x[equ-1-i]=0;
     for(int i=k-1;i>=0;i--)
     {
        int tmp=a[i][var];
        for(int j=i+1;j<var;j++)
          tmp=((tmp-a[i][j]*x[j])%2+2)%2;
        x[i]=tmp/a[i][i]%2;
     }
     int cnt=0;
     for(int i=0;i<var;i++)
        if(x[i]) cnt++;
     ret=min(cnt,ret);
     if(ret==0) break;
   }*/     // 二進制枚舉 
     int Min=inf; 
     for(int j=0;j<(1<<(equ-k));j++) 
     { 
        int tmp=j,p=equ-1; 
        while(tmp) x[p--]=tmp%2,tmp>>=1; 
        for(int i=k-1;i>=0;i--) 
        { 
          int tmp=a[i][var]%2; 
          for(int j=i+1;j<var;j++) 
             if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%2+2)%2; 
          x[i]=(tmp/a[i][i])%2; 
        } 
        tmp=0; 
        for(int i=0;i<var;i++) tmp+=x[i]; 
        Min=min(Min,tmp); 
        if(Min==0) 
        break; 
     }   //全部枚舉 
   return Min; 
} 
int main() 
{ 
    int T; 
 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d",&n); 
        init(); 
       // debug(); 
        int re=gauss(); 
        //cout<<re<<endl; 
        if(re==inf) puts("inf"); 
        else printf("%d\n",re); 
    } 
 
    return 0; 
} 

http://poj.org/problem?id=1753
同上，不貼代碼了
http://poj.org/problem?id=3185
沒什麼特別的
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3858
枚舉四種圖案，沒什麼特別的
http://acm.hdu.edu.cn/showproblem.php?pid=4200
連動題
[cpp]
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
 
using namespace std; 
const int maxn=101; 
const int inf=0x3fffffff; 
int a[maxn][maxn+1],x[maxn]; 
int equ,var,free_num; 
int n,m; 
int gcd(int a,int b) 
{ 
     if(a<0) return gcd(-a,b); 
     if(b<0) return gcd(a,-b); 
     return b==0?a:gcd(b,a%b); 
} 
int Gauss() 
{ 
    int k,col=0; 
    for(k=0;k<equ&&col<var;k++,col++) 
    { 
        int mx=k; 
        for(int i=k+1;i<equ;i++) 
          if(a[i][col]>a[mx][col]) mx=i; 
        if(mx!=k) 
           for(int i=k;i<var+1;i++)  swap(a[k][i],a[mx][i]); 
        if(!a[k][col]) { k--;continue; } 
        for(int i=k+1;i<equ;i++) 
           if(a[i][col]!=0) 
           { 
               int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col]; 
               int ta=lcm/a[i][col],tb=lcm/a[k][col]; 
               if(a[i][col]*a[k][col] < 0)  tb = -tb; 
               for(int j=col;j<var+1;j++) 
                 a[i][j]=((a[i][j]*ta)%2 - (a[k][j]*tb)%2+2)%2; 
           } 
     } 
 
     for(int i=k;i<equ;i++) 
        if(a[i][var]) return inf; 
     for(int i=0,j;i<equ;i++) 
         if(!a[i][i]) 
         { 
              for(j=i+1;j<var;j++) 
                 if(a[i][j]) break; 
              if(var==j) break; 
              for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); 
         } 
 
     int ret=inf; 
     long long lim= (1<<(var-k)); 
 
   for(long long  j=0;j<lim;j++) 
   { 
     for(int i=0;i<(var-k);i++) 
       if(j&(1<<i)) x[equ-1-i]=1; 
       else x[equ-1-i]=0; 
     for(int i=k-1;i>=0;i--) 
     { 
        int tmp=a[i][var]; 
        for(int j=i+1;j<var;j++) 
          tmp=((tmp-a[i][j]*x[j])%2+2)%2; 
        x[i]=tmp/a[i][i]%2; 
     } 
     int cnt=0; 
     for(int i=0;i<var;i++) 
        if(x[i]) cnt++; 
     ret=min(cnt,ret); 
     if(ret==0) break; 
   } 
 
     return ret; 
} 
void  init() 
{ 
     memset(a,0,sizeof(a)); 
     memset(x,0,sizeof(x)); 
     for(int i=0;i<n;i++) 
     { 
         scanf("%d",&a[i][var]); 
         a[i][i]=1; 
     } 
     for(int i=0;i<n;i++) 
     { 
         int p,q; 
        if(i-m>=0) p=i-m;else p=0; 
        if(i+m<n) q=i+m;else q=n-1; 
        for(int j=p;j<=q;j++) 
           a[j][i]=1; 
     } 
     return ; 
} 
int main() 
{ 
    int t; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d%d",&n,&m); 
        //cout<<"*"<<endl; 
        equ=n;var=n; 
        init(); 
        int ans=Gauss(); 
        if(ans==inf) puts("impossible"); 
        else printf("%d\n",ans); 
    } 
    return 0; 
} 

http://poj.org/problem?id=2947
同余題
[cpp]
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
 
using namespace std; 
const int maxn=301; 
const int inf=0x3fffffff; 
int a[maxn][maxn+1],x[maxn]; 
int equ,var,free_num; 
char str[8][4]={"MON","TUE","WED","THU","FRI","SAT","SUN"}; 
__int64 exGcd(__int64 a,__int64 b, __int64 &xx, __int64 &yy) 
{ 
       if(b == 0) 
       { 
       xx = 1; 
       yy = 0; 
       return a; 
       } 
       __int64 r = exGcd(b, a % b, xx, yy); 
       __int64 t = xx; 
       xx = yy; 
       yy = t - a / b * yy; 
    return r; 
} 
int gcd(int a,int b) 
{ 
     if(a<0) return gcd(-a,b); 
     if(b<0) return gcd(a,-b); 
     return b==0?a:gcd(b,a%b); 
} 
void Gauss() 
{ 
 
    int k,col=0; 
    __int64 xx,yy; 
    for(k=0;k<equ&&col<var;k++,col++) 
    { 
        int mx=k; 
        for(int i=k+1;i<equ;i++) 
          if(abs(a[i][col])>abs(a[mx][col])) mx=i; 
        if(mx!=k) 
           for(int i=k;i<var+1;i++)  swap(a[k][i],a[mx][i]); 
        if(!a[k][col]) { k--;continue; } 
        for(int i=k+1;i<equ;i++) 
           if(a[i][col]!=0) 
           { 
               int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col]; 
               int ta=lcm/a[i][col],tb=lcm/a[k][col]; 
               if(a[i][col]*a[k][col] < 0)  tb = -tb; 
               for(int j=col;j<var+1;j++) 
                 a[i][j]=((a[i][j]*ta)%7 - (a[k][j]*tb)%7+7)%7; 
           } 
     } 
     for(int i=k;i<equ;i++) 
        if(a[i][col]!=0) {puts("Inconsistent data.");return ;} 
        if(var>k){puts("Multiple solutions.");return ;} 
    for(int i=0,j;i<equ;i++) 
         if(a[i][i]==0) 
         { 
              for(j=i+1;j<var;j++) 
                 if(a[i][j]) break; 
              //if(var==j) break; 
              if(j>=var) break; 
              for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); 
         } 
 
      for(int i=k-1;i>=0;i--) 
      { 
          int tmp=a[i][var]%7; 
          for(int j=i+1;j<var;j++) 
          if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%7+7)%7; 
       __int64 d=exGcd(a[i][i],7,xx,yy); 
       if(tmp%d!=0){puts("Inconsistent data.");return ;} 
       else{ 
              x[i]=tmp/d*xx%7+7; 
              x[i]=x[i]%(7/d); 
            } 
            while(x[i]<3) x[i]=x[i]+7; 
      } 
 
      for(int i=0;i<var;i++) 
      { 
          if(i==0) cout<<x[i]; 
          else cout<<" "<<x[i]; 
      } 
      puts(""); 
 
} 
 
 
void  init() 
{ 
     memset(a,0,sizeof(a)); 
     memset(x,0,sizeof(x)); 
     int d; 
     char s1[4],s2[4]; 
     for(int i=0;i<equ;i++) 
     { 
         scanf("%d%s%s",&d,s1,s2); 
         int q1,q2; 
         for(int j=0;j<8;j++) 
         if(!strcmp(s1,str[j])){q1=j;break;} 
         for(int j=0;j<8;j++) 
         if(!strcmp(s2,str[j])){q2=j;break;} 
         while(d--) 
         { 
             int num; 
             scanf("%d",&num); num--;a[i][num]++; 
             a[i][num]%=7; 
         } 
         a[i][var]=(q2-q1+1+7)%7; 
     } 
     return ; 
} 
int main() 
{ 
    while(scanf("%d%d",&var,&equ)!=EOF) 
    { 
        if(var==0&&equ==0) break; 
        init(); 
        Gauss(); 
    } 
    return 0; 
}