高斯消元一

题目链接： 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;

}

巴特西

[hihoCoder] 高斯消元·一 [TPLY]