P2455 [SDOI2006]线性方程组 题解
FriedrichC · · 题解
题目传送门
本题的前置知识：P3389 【模板】高斯消元法。
关于如何进行常规的高斯消元或者高斯-约旦消元，许多题解已经讲得非常清楚了，本文不再过多赘述，
这道题真正的难点在于，如何判断无解和无穷解的情况，以及如何正确处理解的表达，
本篇题解将以这几个问题为重点，通过几组整合自讨论版的 hack 数据来讲解。
先展示代码
#include<bits/stdc++.h>
#define db double
using namespace std;
db a[110][110],ans[110];
const db eps=1e-8;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n+1;++j)cin>>a[i][j];
int res=1;
for(int i=1;i<=n;++i)
{
int r=res;
for(int j=res+1;j<=n;++j)
if(fabs(a[r][res])<fabs(a[j][res]))r=j;
if(res!=r)swap(a[res],a[r]);
db temp=a[res][i];
if(fabs(temp)<eps)continue;
for(int j=i;j<=n+1;++j)
a[res][j]/=temp;
for(int j=res+1;j<=n;++j)
{
temp=a[j][i];
for(int k=res;k<=n+1;++k)
a[j][k]-=a[res][k]*temp;
}
res++;
}
ans[n]=a[n][n+1];
if(fabs(ans[n])<eps)ans[n]=0;
for(int i=n-1;i>=1;--i)
{
ans[i]=a[i][n+1];
for(int j=i+1;j<=n;++j)
ans[i]-=a[i][j]*ans[j];
if(fabs(ans[i])<eps)ans[i]=0;
}
bool mark=0;
for(int i=1;i<=n;++i)
{
bool ok=0;
for(int j=1;j<=n;++j)
{
if(fabs(a[i][j])>eps)
{
ok=1;
break;
}
}
if(!ok)
{
if(fabs(a[i][n+1])>eps)
{
cout<<-1<<endl;
return 0;
}
else mark=1;
}
}
if(mark)
{
cout<<0<<endl;
return 0;
}
for(int i=1;i<=n;++i)printf("x%d=%.2lf\n",i,ans[i]);
return 0;
}细节讲解
以下内容以高斯消元的算法处理为主。
数据处理
先来看这样一组数据：
input:
3
5 1 5 3
5 4 1 3
5 5 2 3
output:
x1=0.60
x2=0.00
x3=0.00假如我们不对计算出的答案做任何判断的处理，直接输出答案，那么我们可能会得到 x3=-0.00 这样的结果。
因为浮点数计算时一定存在精度误差，所以我们可能无法准确计算出刚好为
但是由于答案保留两位小数，我们显然会认为这样的答案就是在数值上等同于
if(fabs(ans[i])<eps)ans[i]=0;
需要注意的是，既然我们有了上述的认识，我们就要意识到，在本题中所有需要判断数据是否等于
解的判定
现在，我们来讲解判断无解和无穷解时需要注意的事项。
我们肯定是优先判断无解，再判断无穷解，因为如果满足一个无穷解的条件不代表最终这个方程一定不是无解，但是满足一个无解的条件，这个方程一定无解，也就是无解的条件具有更高优先级，这一点在其他题解中已经写得很清楚了。
显然我们是在最后回带结束，求出每个
那么首先，在消元的过程当中，如果遇到除数为
if(fabs(temp)<eps) continue;
如果不记得跳过的话，可能在消元某个矩阵的过程中会出现这样的情况：
1.00 1.00 1.00 1.00 0.00
0.00 nan inf inf inf
0.00 nan nan nan nan
0.00 nan nan nan nan很可能导致最终答案一律变为
然后，我们进入到具体的判定过程，
如果仅仅像这样：
if(fabs(a[i][i])<eps&&fabs(ans[i])>eps)
{
cout<<-1<<endl;
return 0;
}
if(fabs(a[i][i])<eps&&fabs(ans[i])<eps)......;每行只判断两个数的值是不够的。
看下面这组数据：
intput:
4
0 0 2 4 6
0 0 1 1 2
0 0 4 8 12
1 1 1 1 0
output:
0如果类似上述代码那样的消元，最后一轮矩阵会消成这样：
1.00 1.00 1.00 1.00 0.00
0.00 0.00 1.00 1.00 2.00
0.00 0.00 1.00 2.00 3.00
0.00 0.00 0.00 0.00 0.00那么如果只判断两个数，输出就会是
所以我们要仔细地检查每一个数，就像上面的代码那样：
bool mark=0;
for(int i=1;i<=n;++i)
{
bool ok=0;
for(int j=1;j<=n;++j)
{
if(fabs(a[i][j])>eps)
{
ok=1;
break;
}
}
if(!ok)
{
if(fabs(a[i][n+1])>eps)
{
cout<<-1<<endl;
return 0;
}
else mark=1;
}
}
if(mark)
{
cout<<0<<endl;
return 0;
}消元时的细节
最后需要注意的是，在消元的过程之中，我们还需要一个
这组数据就很好地阐明了它的作用：
input
2
0 2 4
0 2 3
output:
-1假如不使用类似的一个指针的话，常规消元得到的结果可能是这样的：
0.00 2.00 4.00
0.00 1.00 1.50正如我们所见，这相当于根本没消元。
没有消元的原因在于，第一行的主元是找不到的，所以处理第一行时会跳过这一轮，然后就会处理第二行，
然而第二行是最后一行了，不会去处理其他行，所以总体上我们根本没消元，
那么自然，这组数据最终会输出一组解，但是这是不对的。
因此我们才需要一个类似
我们可以对比一下常规高斯消元的代码：
int r=i;
for(int j=i+1;j<=n;++j)
if(fabs(a[r][i])<fabs(a[j][i]))r=j;
if(fabs(a[r][i])<eps)continue;
if(i!=r)swap(a[i],a[r]);
db temp=a[i][i];
for(int j=i;j<=n+1;++j)
a[i][j]/=temp;
for(int j=i+1;j<=n;++j)
{
temp=a[j][i];
for(int k=i;k<=n+1;++k)
a[j][k]-=a[i][k]*temp;
}可以看到，在消元时，
但是
然而事实并非如此，像上面的那组数据的第一轮消元实际上就是不成功的。
因此我们需要一个根据我们实际消元情况进行来变化的指针，
如我们所见，在代码中，如果本轮触发了 if(fabs(temp)<eps)continue; 这就说明本轮消元不成功，
然而如果我们的消元正常进行，在每轮的末尾有 res++; 让
如果用上面那组数据来具体说明，那么我们第一行时没有正常消元，在到第二轮时，我们就不应该用第二行进行消元，而还是用第一行进行消元。
这是引入了
0.00 1.00 2.00
0.00 0.00 -1.00这样就成功进行了整体的消元，然后我们也能正确地判断答案了。