https://www.luogu.com.cn/problem/P3389
主元消元法【模板】
高斯消元是解决多元线性方程组的方法，再学习它之前，先引入一个东西——行列式
行列式的性质：
这里我们只说其中的两条：
①行列式中的一行，加上另一行的\(k\)倍，行列式的值不变
②交换行列式的两行，行列式的值会变为原来的相反数
每一个有唯一解的线性方程，都拥有一个与其对应的行列式
//如果想详细学习行列式，可以自行上网百度~
目的：为了方便求解，利用①性质，我们可以把它消成上三角行列式（矩阵的对角线的左下方都是\(0\)），其实通俗来讲，就是平时我们学的加减消元法
具体步骤：
①枚举\(1-n\)行
②用第i行的第i列（对角线上的数）来消\(i+1-n\)行的第\(i\)列数，即:将这些数都加上\(k\times c[i][i]\;\;(k=-\frac{c[j][i]}{c[i][i]})\)
这里必须要注意，\(c[i][i]\)不能是\(0\)，导致没有意义。所以在算倍数k之前，要保证\(c[i][i]≠0\)，即从\(i-n\)行中找到一个数，使得\(c[j][i]≠0\)，然后将这两个行的数交换过来即可
根据行列式性质②，行列式的值要变号，但这里我们是在求方程组，不用管行列式值符号的问题
③然后，自下向上递推。从而求出每一个未知数的解
代码：
void gauss()
{
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
if(fabs(c[j][i])>1e-8)
//找到大于0的除
{
if(j==i)break;
for(int l=1;l<=n+1;l++)
swap(c[j][l],c[i][l]);
break;
}
if(fabs(c[i][i])<=1e-8)continue;
//如果这列已经全是0了，不必继续消了
for(int j=i+1;j<=n;j++)
{
double k=c[j][i]/c[i][i];
for (int l=1;l<=n+1;l++)
c[j][l]=c[j][l]-c[i][l]*k;
//k（倍数），把这列的数都消成0
}
}
}
但是这种方法可能会存在精度的问题，算\(k\)（倍数）时出现误差
如何提高精度？
主元消元法
假设现在有个数\(p\)，还有两个数\(10^5,10^{-5}\)
那么\(p\)除以哪个数，分到的小数位数（精度）越高呢？
显然，是\(10^5\)。那么根据我们推导的结论，除数绝对值越大越好
然后我们仔细观察朴素消元的代码
会惊奇的发现只有一行对精度会有影响：
double k=c[j][i]/c[i][i];
根据我们刚刚推导的结论，\(c[i][i]\)绝对值越大，精度越高
因此，我们只需把朴素代码中的找不为\(0\)的数改成找绝对值最大的数即可
void gauss()
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(fabs(c[j][i])>fabs(c[i][i]))//找最大值
{
for(int k=1;k<=n+1;k++)
{
swap(c[j][k],c[i][k]);
}
}
}
if(fabs(c[i][i])<=1e-8)continue;//若全为0，不必继续消
for(int j=i+1;j<=n;j++)
{
double t=c[j][i]/c[i][i];
for(int k=1;k<=n+1;k++)
{
c[j][k]=c[j][k]-t*c[i][k];
}
}
}
}
这样我们就大大提高了算法的精度
还剩最后一个问题：如何判断有多组解的情况？
只需判断某一行消完后是否全为\(0\)即可（自己稍微想想即可）
详见完整代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=20;
int n;
double b[N][N],c[N][N],res[N];
void gauss()
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(fabs(c[j][i])>fabs(c[i][i]))
{
for(int k=1;k<=n+1;k++)
{
swap(c[j][k],c[i][k]);
}
}
}
if(fabs(c[i][i])<=1e-8)continue;
for(int j=i+1;j<=n;j++)
{
double t=c[j][i]/c[i][i];
for(int k=1;k<=n+1;k++)
{
c[j][k]=c[j][k]-t*c[i][k];
}
}
}
}
int main()
{
scanf("%d",&n);
for(int a=1;a<=n;a++)
for(int b=1;b<=n+1;b++)
{
scanf("%lf",&c[a][b]);
}
guass();
for(int i=1;i<=n;i++)
{
bool fail=true;
for(int j=1;j<=n+1;j++)
{
if(c[i][j])
{
fail=false;
break;
}
}
if(fail)//若某行的系数全为0，则说明无唯一解
{
puts("No Solution");
return 0;
}
}
for(int i=n;i>=1;i--)
{
double t=0;
for(int j=i+1;j<=n;j++)
{
t=t+res[j]*c[i][j];
}
res[i]=(c[i][n+1]-t)/c[i][i];
}
for(int i=1;i<=n;i++)printf("%.2lf\n",res[i]);
return 0;
}