【高斯消元】GYM-102426A 题解

题意:T组 n个m维的向量 判线性相关
思路:裸的高消,考场的时候因为没有非异或的高消板子和精度问题卡了半天,所以写个方便整理板子。

#include<bits/stdc++.h>
#define clr(x) (x, 0, sizeof x)

using namespace std;

const int maxn = 15;
const int maxm = 5;
int T,n,m;
double tmp,c[maxn][maxn];

int main() {
    scanf("%d",&T);
    while(T--) {
        int f = 0;
        scanf("%d%d",&n,&m);
		clr(c);
        for(int i = 1; i <= n; i++) {
            tmp = 0;
            for(int j = 1; j <= m; j++) scanf("%lf",&c[i][j]), tmp += c[i][j];
            if(!tmp) f = 1;
        }
        if(f || n > m) { printf("YES\n");continue; }
        for(int i = 1; i <= m; i++) {
            int acl = 0;
            for(int j = i; j <= n; j++) if(fabs(c[j][i]) > 1e-8) for(int k = 1; k <= m; k++) swap(c[i][k], c[j][k]), acl = 1;
            if(!acl) continue;
            for(int j = 1; j <= n; j++) if(j != i) {
                if(fabs(c[i][i]) < 1e-8) continue;
                double rate = c[j][i]/c[i][i];
                for(int k = 1; k <= m; k++) c[j][k] -= c[i][k]*rate;
            }
        }
        for(int i = 1; i <= n; i++) {
            double tmp =  0;
            for(int j = 1; j <= m; j++) if(fabs(c[i][j]) > 1e-8) tmp++;
            if(tmp == 0) f = 1;
        }
		printf(f ? "YES\n" : "NO\n");
    }
    return 0;
}

上一篇:数学计算 —— 圆周率


下一篇:(Python)Gurobi求解最大流问题