高斯消元一

题目链接 : http://hihocoder.com/problemset/problem/1195?sid=1269842

“好aoaoaoaoaoaoa”的高斯消元模板题

题意

多个方程组,要求:输出解、判无解、判多解
保证方程解非负

做法

第一点注意

首先要会高斯消元(废话)
然后还要卡精度
所以一定要用eps卡精度
这是第一点

第二点注意

然后就是最恶心的:判无解多解
我们先明确一点:无解优先级大于多解
什么意思呢?
对于一个方程,我们要先检查无解,再检查多解
明白这一点之后,咱们继续。

第三点注意

无解怎么判断?
如果 方程系数都等于0并且结果大于 0 则无解(因为题目保证解是非负数)
(形如 x × 0 = y , x × -1 = y | x>0 && y>0,肯定无解)

第四点注意

如何判断多解?
如果在消元过程中,某一列都被消成了0,并且保证该方程有解,那么这个方程是多解的。
为什么呢?
因为如果一个未知数上的系数都是0,那么这个未知数有无穷多种取法,所以方程就有多组解了。

第五点注意

如果你发现有多解,但是不确定是不是无解怎么办?
如果在最后用倒三角求未知数的值时
我们求到一个未知数的系数为0
但是它的值不为0的时候
那么它就是无解的
反之就是多解的

总结

综上所述 这道题是“不折不扣”“模板题”

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define rg register int
#define ll long long
#define RG register
#define il inline
using namespace std;

il int gi() 
{
    rg x=0,o=0;RG char ch=getchar();
    while(ch!='-'&&(ch<'0'||'9'<ch)) ch=getchar();
    if(ch=='-') o=1,ch=getchar();
    while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return o?-x:x;
}

int n,m;
#define db double
db x[1001],fc[1001][501];

il int gauss()
{
    RG bool flg=0;
    for(rg now,k=1; k<=n; ++k)
    {
        now=k;
        for(rg i=k+1; i<=m; ++i)
            if(fabs(fc[i][k])>fabs(fc[now][k]))
                now=i;
        if(now==k && fabs(fc[k][k])<1e-7) 
        {
            flg=1;
            continue;
        }
        if(now!=k) swap(fc[now],fc[k]);
        for(rg i=k+1; i<=n+1; ++i) fc[k][i]/=fc[k][k];fc[k][k]=1;
        for(rg i=k+1; i<=m; ++i)
        {
            for(rg j=k+1; j<=n+1; ++j)
                fc[i][j]-=fc[i][k]*fc[k][j];
            fc[i][k]=0;
        }
    }
    for(rg j,i=1; i<=m; ++i)
    {
        for(j=1; j<=n; ++j)
            if(fabs(fc[i][j])>1e-6)
                break;
        if(j==n+1 && fabs(fc[i][n+1])>1e-6) return 0; // 如果 方程系数小于0并且结果大于 0 则无解
    }
    for(rg i=n; i>=1; --i)
    {
        for(rg j=i+1; j<=n; ++j) fc[i][n+1]-=fc[i][j]*fc[j][n+1];
        if(fc[i][n+1] && !fc[i][i] ) return 0;
    }
    if(flg) return -1;
    return 1;
}
int main() 
{
    n=gi(),m=gi();
    for(rg i=1; i<=m; ++i)
        for(rg j=1; j<=n+1; ++j)
            scanf("%lf",&fc[i][j]);
    rg ans=gauss();
    if(ans==-1) puts("Many solutions");
    else if(ans==0) puts("No solutions");
    else for(rg i=1; i<=n; ++i) printf("%d\n",(int)(fc[i][n+1]+0.5));
    return 0;
}
分类: 所有

TPLY

我是最弱的

6 条评论

konnyakuxzy · 2018年2月10日 1:39 下午

顺带一提,您这篇文章是k-xzy的第400篇文章
QvQ
(作为博主我居然让这个荣誉被抢走了QvQ)

    TPLY · 2018年2月10日 2:12 下午

    哇啊啊
    荣幸荣幸

konnyakuxzy · 2018年2月10日 1:37 下午

Orz太强了
话说您为啥这么喜欢文乃酱啊?

    TPLY · 2018年2月10日 2:12 下午

    喜欢还需要理由吗?

      konnyakuxzy · 2018年2月10日 2:31 下午

      QvQ
      当然不是啦
      只是,,,好奇
      比如我很喜欢爱蜜莉雅就是因为
      她很卡哇伊QvQ

        TPLY · 2018年2月10日 2:38 下午

        其实我也找不出特别的理由。。
        QvQ
        就是喜欢啦

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *