首页 > 代码库 > 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异或的高斯消元)