高斯消元模板
发布日期:2021-07-14 01:03:48 浏览次数:45 分类:技术文章

本文共 3493 字,大约阅读时间需要 11 分钟。

整数类型高斯消元

返回值的情况

  • -2表示有浮点数解,但无整数解
  • -1表示无解
  • 0表示唯一解
  • 大于0表示无穷解,并返回自由变元的个数

    其他说明

  • 有equ个方程,var个变元。
  • 增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.

    Code

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
    #include 
    #include
    #include
    #define nmax 100 using namespace std; int a[nmax][nmax]; int x[nmax]; int free_x[nmax]; int gcd(int a,int b){
    if(!b) return a; else return gcd(b,a%b); } int lcm(int a,int b){
    return a/gcd(a,b)*b; } int Gauss(int equ,int var){
    int k,max_r,col = 0,ta,tb; int LCM,temp,num = 0,free_index; for(int i=0;i<=var;i++){
    x[i]=0; free_x[i]=true; } for(k = 0;k < equ && col < var;k++,col++){
    max_r=k; for(int i=k+1;i
    abs(a[max_r][col])) max_r=i; } if(max_r!=k){
    // 与第k行交换. for(int j=k;j
    = 0; i--){
    temp = a[i][var]; for (int j = i + 1; j < var; j++){
    if (a[i][j] != 0) temp -= a[i][j] * x[j]; } if (temp % a[i][i] != 0) return -2; // 说明有浮点数解,但无整数解. x[i] = temp / a[i][i]; } return 0; }

浮点类型

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
#include 
#include
#include
#include
#include
using namespace std; const int N = 1010; const double EPS=1e-7; int m,n; double a[N][N],x[N]; int Gauss(int m,int n){
int col=0, k=0;//col为列号,k为行号 for (;k
fabs(a[r][col]))r=i; if (fabs(a[r][col])
EPS){ double t = a[i][col]/a[k][col]; for (int j=col;j<=n;j++)a[i][j]-=a[k][j]*t; a[i][col] = 0; } } for(int i=k ;i
EPS) return -1; if (k < n) return n - k; //自由元个数 for (int i =n-1; i>=0; i--){ //回带求解 double temp = a[i][n]; for (int j=i+1; j

求解异或方程组

经常需要枚举自由元

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
#include 
#include
#include
#include
#define nmax 35 using namespace std; int a[nmax][nmax]; int x[nmax]; int hashback[nmax][nmax]; int free_x[nmax]; char mp[nmax][nmax]; int ans1,ans2; int equ,var; int Gauss(){
int max_r; int col=0,num = 0; int k; for(int i = 0;i<=var;++i) x[i] = free_x[i] = 0; for(k = 0;k < equ && col < var;k++,col++){
max_r=k; for(int i=k+1;i
abs(a[max_r][col])) max_r=i; } if(max_r!=k){
for(int j=k ;j
= 0; i--){ x[i]=a[i][var]; for(int j = i + 1; j < var; j++){ x[i] ^= ( a[i][j] && x[j]); } } return 0; } void enum_freex(int n,int & ans){ int num = (1<<(n)); ans = 1e9+7; for(int i = 0;i
=0;--k){ // 没有自由元的最下面一行 int index = 0; for(index = k;k

取自[pengwill97 ][ ]

转载地址:https://blog.csdn.net/cpongo3/article/details/89334325 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Intervals
下一篇:P3379 【模板】最近公共祖先(LCA)

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月06日 22时13分14秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章