朝田诗乃 的博客

朝田诗乃 的博客

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

posted on 2019-10-09 22:32:06 | under 题解 |

这题很可爱,所以诗乃想用比较简单可爱的高斯-约旦消元写。(主要还是因为诗乃太菜了看不懂什么矩阵搞来搞去的)

大致思路:直接跑高斯-约旦消元,然后最后得到一些式子:

$$k_1a_1 = b_1$$ $$k_2a_2=b_2$$ $$k_3a_3=b_3$$ $$.......$$

按照套路先判无解再判无穷解,若存在某方程 $k=0$ 但 $b≠0$ ,则无解,否则若有某方程 $k=0$ 且 $b=0$ ,则有无穷解。

消元时如果存在一些主元的系数全部为0,则将这些主元留到最后消,否则会造成某些主元系数无法消除的情况。

(其实假装分一个方程给它就好了反正也消不掉什么东西)

#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。