题解 P2455 【[SDOI2006]线性方程组】

· · 题解

xyw学长:noip高斯消元都是板子题

但是，但是，但是

你得找一个正确的板子打啊......

qwq我自己学的高斯消元然后一直是错的qwq

但高斯消元模板题数据相当水然后我就过了qwq

这题才是真·模板题

目前看到的有两种写法

一种是找j=i~n行中f[j][i]最大的，把它和第i行交换，然后下面消元的时候从1~n行消1~n+1列

一种是把i~n行sort，消元的时候从i+1~n行消i~n列

楼下两个神犇分别用了这两种方法

我用的第一种

效率不明，第一种大概常数是第二种的6倍，第二种加了sort的nlogn复杂度

但这题数很小所以0ms都能过

我也没测试过具体哪个快qwq

高斯消元你要是思想就去百(goo)度(gle)

直接看代码及注释就好了

#include<cstdio>
using namespace std;
const double eps=1e-5;//注意，实型的精度问题导致不能直接比较一般来说会定义一个eps
//a>b:a-b>eps,其它同
double a[51][51],f[51]={0};
int n;
int getin()//常见的快读，这还是我半年之前写的版本
{
    char ch=getchar();int x=0,f=1;
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return f*x;
}
double abs1(double t)//cmath的自带fabs怕出事...库函数的pow和abs最好自己写，不然容易出事
{
    if(t<0)return -t;return t;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            a[i][j]=getin();//增广矩阵读入，a[i][n+1]是每个方程右边的值
    for(int i=1;i<=n;i++)
    {
        int k=i;
        double t;
        for(int j=i+1;j<=n;j++)if(abs1(a[k][i])<abs1(a[j][i]))k=j;//找最大的交换
        if(k!=i)for(int j=1;j<=n+1;j++)t=a[k][j],a[k][j]=a[i][j],a[i][j]=t;
        if(abs1(a[i][i])>=eps)//如果a[i][i]!=0
            for(int j=1;j<=n;j++)
            { 
                if(i!=j)//不要把自己消了
                {
                    t=a[j][i]/a[i][i];
                    for(int k=1;k<=n+1;k++)
                        a[j][k]-=t*a[i][k];
                }
            }//正常的高斯消元
    }
    int wq=0,wj=0;
    for(int i=1;i<=n;i++)
    {
        int j=1;
        while(abs1(a[i][j])<eps&&j<=n+1)j++;
        if(j>n+1)wq=1;
        if(j==n+1)wj=1; 
    }//判断解的情况，一行全为0则无穷解，前n个为0第n+1个不为0是无解
    //至于为什么是这样，讨论区的一个大神说了
    if(wj){printf("-1");return 0;}//先判断无解
    if(wq){printf("0");return 0;}
    for(int i=n;i>=1;i--)
    {
        for(int k=i+1;k<=n;k++)
            a[i][n+1]-=a[i][k]*f[k];
        f[i]=a[i][n+1]/a[i][i];//普普通通的统计答案
    }
    for(int i=1;i<=n;i++)
        printf("x%d=%.2lf\n",i,f[i]);//普普通通的输出
}

代码丑的一匹请见谅

毕竟我高斯消元一直写得挺懵逼qaq