高斯消元
高斯消元适用于求解线性方程。
线性方程
形如
\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n=b_2\\...\\a_{n,1}x_1+a_{n,2}x_2+...+a_{n,n}x_n=b_n\\\end{cases} \]的方程，我们称之为线性方程。
系数矩阵
我们可以将它们的系数提出来组成一个矩阵，我们称之为系数矩阵。如下。
\[\begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \end{bmatrix} \]矩阵的行变换（列变换）
1.将矩阵的第 \(i\) 行和第 \(j\) 行元素互换；
2.将矩阵的第 \(i\) 行元素分别乘 \(val\)；
3.将矩阵的第 \(i\) 行元素分别乘 \(val\) 再加到第 \(j\) 行的对应位置。
由于矩阵可以倒置，行变换与列变换等价。
增广矩阵
定义：系数矩阵右侧加一列，这一列为方程等式右边的数值。
如下。
\[\begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}&b_1\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}&b_2\\ \vdots & \vdots & \ddots & \vdots&\vdots\\ a_{n,1} & a_{n,2} & \cdots & a_{n,n}&b_n \end{bmatrix} \]行阶梯矩阵
定义：非零行的第一个非零元素的列下标随着行数增加而严格递增，全零元素的行在末尾。
如下。
\[\begin{bmatrix} c_{1,1} & c_{1,2} & c_{1,3} & \cdots & c_{1,n}&d_1\\ 0 & c_{2,2} & c_{2,3} & \cdots & c_{2,n}&d_2\\ 0&0&c_{3,3}&\cdots &c_{3,n} & d_3\\ \vdots & \vdots &\vdots& \ddots & \vdots&\vdots\\ 0 & 0 & 0&\cdots & c_{n,n}&d_n \end{bmatrix} \]方程组解的判定
矩阵的行秩（rank）：行阶梯矩阵非零行的数量 \(r\)；
1.有唯一解：增广矩阵行秩 \(=\) 未知数数量；
2.有无数多组解：增广矩阵的行秩 \(<\) 未知数的数量；
3.无解：系数矩阵的行秩 \(\not=\) 增广矩阵的行秩。
复杂度 \(O(3)\)
例一 P3389【模板】高斯消元法
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int n;
double a[MAXN][MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++) scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++)
{
int maxn=i;
for(int j=i+1;j<=n;j++)
if(abs(a[j][i])>abs(a[maxn][i])) maxn=j;
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[maxn][j]);
if(fabs(a[i][i])<0.001) {printf("No Solution\n");return 0;}
for(int j=1;j<=n;j++)
{
if(i==j) continue;
double rate=a[j][i]*1.0/a[i][i];
for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*rate;
}
}
for(int i=1;i<=n;i++)
{
double ans=a[i][n+1]*1.0/a[i][i];
printf("%.2lf\n",ans);
}
return 0;
}
例二 P2455 [SDOI2006]线性方程组
真正意义上的高斯消元模板题，将三种情况完全分开了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
const double eps=1e-6;
int n;
double a[MAXN][MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++) scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++)
{
int maxn=i;
for(int j=i+1;j<=n;j++)
if(abs(a[j][i])>abs(a[maxn][i])) maxn=j;
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[maxn][j]);
if(fabs(a[i][i])<eps) continue;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
double rate=a[j][i]*1.0/a[i][i];
for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*rate;
}
}
for(int i=1;i<=n;i++)
{
double sum=0;
for(int j=1;j<=n;j++)
sum+=a[i][j];
if(sum==0 && fabs(a[i][n+1])>=eps) {printf("-1\n");return 0;}
}
for(int i=1;i<=n;i++)
if(fabs(a[i][i])<=eps && fabs(a[i][n+1])<=eps) {printf("0\n");return 0;}
for(int i=1;i<=n;i++)
{
double ans=a[i][n+1]*1.0/a[i][i];
printf("x%d=%.2lf\n",i,ans);
}
return 0;
}
例三 P3164 [CQOI2014]和谐矩阵
只是把高斯消元用在了异或上。
那么我们就将系数全设为 \(1\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int n,m;
int a[MAXN][MAXN];
inline void check()
{
for(int i=m;i>(m+1)>>1;i--)a[1][i]=a[1][m+1-i];
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=a[i-1][j]^a[i-1][j-1]^a[i-1][j+1]^a[i-2][j];
for(int i=1;i<=m;i++)
if(a[n][i]^a[n][i-1]^a[n][i+1]^a[n-1][i]) return;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) printf("%d ",a[i][j]);
puts("");
}
exit(0);
}
inline void dfs(int x)
{
if(x>(m+1)>>1) {check();return;}
a[1][x]=1;dfs(x+1);
a[1][x]=0;dfs(x+1);
return;
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1);
return 0;
}