高斯消元专题 - c++编程基础

由于老师的讲课，我又重拾高斯消元，做了一天的高斯，感觉老师讲得很好，模板也不错，我懒得自己写，就把同僚的模板拿过来用了，反正基本原理都懂了。
高斯消元模板题，只有唯一解。
[cpp]
#include
#include
#include
#include

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 {
for(int j=0;j cout< cout< }
}
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 {
int mx=k;
for(int i=k+1;i if(a[i][col]>a[mx][col]) mx=i;
if(mx!=k)
for(int i=k;i if(!a[k][col]) { k--;continue; }
for(int i=k+1;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 a[i][j]=((a[i][j]*ta)%2 - (a[k][j]*tb)%2+2)%2;
}
}
// Debug();
//cout< for(int i=k;i if(a[i][var]) return -1;
for(int i=0,j;i if(!a[i][i])
{
for(j=i+1;j if(a[i][j]) break;
if(j>=var) break;
for(int r=0;r }

//唯一解
for(int i=k-1;i>=0;i--)
{
int tmp=a[i][var]%2;
for(int j=i+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
#include
#include
#include
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 scanf("%s",s[i]);
memset(a,0,sizeof(a));
for(int i=0;i for(int i=0;i for(int j=0;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 if(j-1>=0) a[i*n+j][i*n+j-1]=1;
if(j+1 }
}
void debug()
{
for(int i=0;i {
for(int j=0;j<=var;j++)
cout< cout< }
cout< }
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 {
int mx=k;
for(int i=k+1;i if(a[i][col]>a[mx][col]) mx=i;
if(k!=mx){
for(int i=k;i swap(a[k][i],a[mx][i]);
}
if(!a[k][col]){
k--;continue;

高斯消元专题(一)