题解 P2455 【[SDOI2006]线性方程组】
诗乃
2019-10-09 22:32:06
这题很可爱，所以诗乃想用比较简单可爱的高斯-约旦消元写。(主要还是因为诗乃太菜了看不懂什么矩阵搞来搞去的)
大致思路：直接跑高斯-约旦消元，然后最后得到一些式子：
$$k_1a_1 = b_1$$
$$k_2a_2=b_2$$
$$k_3a_3=b_3$$
$$.......$$
按照套路先判无解再判无穷解，若存在某方程$k=0$但$b≠0$，则无解，否则若有某方程$k=0$且$b=0$，则有无穷解。
消元时如果存在一些主元的系数全部为0，则将这些主元留到最后消，否则会造成某些主元系数无法消除的情况。
（其实假装分一个方程给它就好了反正也消不掉什么东西）
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150;
const double eps = 1e-8;
int read() {
char ch; int x, f = 1; while(ch = getchar(), ch < '!' || ch == '-') if(ch == '-') f = -1;
x = ch - 48; while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; return x *= f;
}
int n, line, id[MAXN]; double a[MAXN][MAXN];
int main() {
n = read(); srand(time(0));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n+1; ++j)
a[i][j] = read();
line = 1; //分开记录当前方程和当前主元以便调换消元顺序
for(int i = 1; i <= n; ++i) {
int _max = line;
for(int j = line+1; j <= n; ++j)
if(fabs(a[j][i]) > fabs(a[_max][i])) _max = j;
if(!a[_max][i]) continue;
for(int j = 1; j <= n+1; ++j) swap(a[line][j], a[_max][j]);
for(int j = 1; j <= n; ++j) {
if(j == line) continue;
double t = 1.0 * a[j][i] / a[line][i];
for(int k = i+1; k <= n+1; ++k)
a[j][k] -= a[line][k] * t;
} id[i] = line; ++line;
}
vector <int> tt;
for(int i = 1; i <= n; ++i) if(!id[i]) tt.push_back(i);
for(int j = 0; line <= n; ++line, ++j) id[tt[j]] = line;
//给剩下主元随便分配一个剩下的方程
for(int i = 1; i <= n; ++i) if(!a[id[i]][i] && a[id[i]][n+1]) {puts("-1"); return 0;}
for(int i = 1; i <= n; ++i) if(!a[id[i]][i] && !a[id[i]][n+1]) {puts("0"); return 0;}
for(int i = 1; i <= n; ++i) printf("x%d=%.2lf\n", i, fabs(a[id[i]][n+1] / a[id[i]][i]) < eps ? 0.0 : a[id[i]][n+1] / a[id[i]][i]);
}
```
欢迎Hack。