首页 > 代码库 > NEFU 503 矩阵求解 (非01异或的高斯消元)
NEFU 503 矩阵求解 (非01异或的高斯消元)
题目链接
中文题,高斯消元模板题。
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <queue>#include <vector>#include <map>#include <ctime>using namespace std;typedef long long in;const int maxn=300;//有equ个方程,var个变元。增广矩阵行数为equ,列数为var+1,分别为0到varin equ,var;in a[maxn][maxn]; //增广矩阵in x[maxn]; //解集in free_x[maxn];//用来存储自由变元(多解枚举自由变元可以使用)in free_num;//自由变元的个数//返回值为-1表示无解,为0是唯一解,否则返回自由变元个数in gcd(in a,in b){ return b==0?a:gcd(b,a%b);}in lcm(in a,in b){ return a/gcd(a,b)*b;}in gauss(){ in max_r,col,k; free_num=0; for(k=0,col=0; k<equ&&col<var; k++,col++) { max_r=k; for(in i=k+1; i<equ; i++) if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; if(!a[max_r][col]) { k--; free_x[free_num++]=col; continue; } if(max_r!=k) for(in j=col; j<var+1; j++) swap(a[k][j],a[max_r][j]); /*for(int i=k+1;i<equ;i++) { if(a[i][col]) { for(int j=col;j<var+1;j++) a[i][j]^=a[k][j]; } }*/ for(in i=k+1; i<equ; ++i) { if(a[i][col] != 0) { in LCM=lcm(abs(a[i][col]),abs(a[k][col])); in ta=LCM/abs(a[i][col]),tb=LCM/abs(a[k][col]); if(a[i][col]*a[k][col] < 0) tb=-tb; for(in j=col; j<var+1; ++j) a[i][j]=a[i][j]*ta-a[k][j]*tb; } } } for(in i=k; i<equ; i++) if(a[i][col]) return -1; if(k<var) return var-k; for(in i=k-1; i>=0; --i) { in tmp=a[i][var]; for(in j=i+1; j<var; ++j) if(a[i][j]!=0) tmp=tmp-(a[i][j]*x[j]); x[i]=tmp/a[i][i]; } /*for(int i=var-1;i>=0;i--) { x[i]=a[i][var]; for(int j=i+1;j<var;j++) x[i]^=(a[i][j]&&x[j]); }*/ return 0;}in n;void init(){ memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); equ=n; var=n;}void solve(){ in t=gauss(); if(t==-1) { puts("no sovle!"); } else if(t==0) { for(int i=0; i<n-1; i++) printf("%d ",x[i]); printf("%d\n",x[n-1]); } else { puts("more sovle!"); }}int main(){ while(scanf("%lld",&n)!=EOF) { init(); for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%lld",&a[i][j]); for(int i=0; i<n; i++) scanf("%lld",&a[i][n]); solve(); } return 0;}
NEFU 503 矩阵求解 (非01异或的高斯消元)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。