新高斯消元-模板
i207M
2019-07-12 11:05:03
ri，NOI前又和高斯消元奋斗了1h+...为啥只有我写的是假高斯消元...
~~ri，我TM交换行列没交换全，ri~~
先来一个完全正确的版本：
```cpp
int gauss(int n)
{
for(ri i=1,p,c=1;i<=n;++i)
{
for(p=c;p<=n&&!sgn(g[p][i]);++p);
if(p==n+1) continue;
if(p!=c) for(ri j=i;j<=n+1;++j) swap(g[p][j],g[c][j]);
for(ri j=c+1;j<=n;++j)
if(sgn(g[j][i]))
{
double t=g[j][i]/g[c][i];
for(ri k=i;k<=n+1;++k)
g[j][k]-=t*g[c][k];
}
++c;
}
bool inf=0;
for(ri i=n;i>=1;--i)
{
bool hv=0;
for(ri j=i;j<=n;++j)
if(sgn(g[i][j]))
{
hv=1;
break;
}
if(!hv)
{
if(sgn(g[i][n+1])) return -1;
else {inf=1; continue;}
}
ans[i]=g[i][n+1];
for(ri j=i+1;j<=n;++j) ans[i]-=g[i][j]*ans[j];
ans[i]/=g[i][i];
}
return inf?0:1;
}
```
简单的说，就是我们**必须消成全零行**！我们要维护一个列指针i，和行指针c。关于判断无解，我们对每一个等式，看是否左边系数全为0，常数不为0的情况——无解；等于0——无穷解，但是这是不要急着返回，因为可能还有无解的情况。
------------
如果只要判断是否有唯一解，可以用偷懒的方法：
```cpp
for(ri i=1;i<=n;++i)
{
if(!sgn(g[i][i]))
{
int k=-1;
for(ri j=i+1;j<=n;++j)
if(sgn(g[j][i]))
{
k=j;
break;
}
if(k==-1) continue;
for(ri j=i;j<=n+1;++j)
swap(g[i][j],g[k][j]);
}
for(ri j=n+1;j>=i;--j) g[i][j]/=g[i][i];
for(ri j=i+1;j<=n;++j)
if(sgn(g[j][i]))
{
for(ri k=n+1;k>=i;--k)
g[j][k]-=g[j][i]*g[i][k];
}
}
```