模线性方程组

模线性方程组
题目链接：http://poj.org/problem?id=2947
有m条记录，n个零件，那么就是m个方程，n个未知数，然后所花的天数和在工厂呆的天数对7同余，也就是求解一个模线性方程组。
代码：

#include<bits/stdc++.h>
#define MAXN 310
#define N 310
#define MOD 7
using namespace std;



int a[N][N];//增广矩阵
int x[N];//解集
bool freeX[N];//标记是否为自由变元
int GCD(int a,int b){
    return !b?a:GCD(b,a%b);
}
int LCM(int a,int b){
    return a/GCD(a,b)*b;
}
int Gauss(int equ,int var){//返回自由变元个数
    /*初始化*/
    for(int i=0;i<=var;i++){
        x[i]=0;
        freeX[i]=true;
    }

    /*转换为阶梯阵*/
    int col=0;//当前处理的列
    int row;//当前处理的行
    for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
        int maxRow=row;//当前列绝对值最大的行
        for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
            if(abs(a[i][col])>abs(a[maxRow][col]))
                maxRow=i;
        }
        if(maxRow!=row){//与第row行交换
            for(int j=row;j<var+1;j++)
                swap(a[row][j],a[maxRow][j]);
        }
        if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
            row--;
            continue;
        }

        for(int i=row+1;i<equ;i++){//枚举要删去的行
            if(a[i][col]!=0){
                int lcm=LCM(abs(a[i][col]),abs(a[row][col]));
                int ta=lcm/abs(a[i][col]);
                int tb=lcm/abs(a[row][col]);
                if(a[i][col]*a[row][col]<0)//异号情况相加
                    tb=-tb;
                for(int j=col;j<var+1;j++) {
                    a[i][j]=((a[i][j]*ta-a[row][j]*tb)%MOD+MOD)%MOD;
                }
            }
        }
    }

    /*求解*/
    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    for(int i=row;i<equ;i++)
        if (a[i][col]!=0)
            return -1;

    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
    int temp=var-row;//自由变元有var-row个
    if(row<var)//返回自由变元数
        return temp;

    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for(int i=var-1;i>=0;i--){//计算解集
        int temp=a[i][var];
        for(int j=i+1;j<var;j++){
            if(a[i][j]!=0)
                temp-=a[i][j]*x[j];
            temp=(temp%MOD+MOD)%MOD;//取模
        }
        while(temp%a[i][i]!=0)//外层每次循环都是求a[i][i]，它是每个方程中唯一一个未知的变量
            temp+=MOD;//a[i][i]必须为整数，加上周期MOD
        x[i]=(temp/a[i][i])%MOD;//取模
    }
    return 0;
}
//

int sts(char* s)
{
    if(strcmp(s,"MON")==0) return 1;
    else if(strcmp(s,"TUE")==0) return 2;
    else if(strcmp(s,"WED")==0) return 3;
    else if(strcmp(s,"THU")==0) return 4;
    else if(strcmp(s,"FRI")==0) return 5;
    else if(strcmp(s,"SAT")==0) return 6;
    else if(strcmp(s,"SUN")==0) return 7;

}

char s1[5], s2[5];

int main()
{
    int n, m; 
    int equ, var;
    while(~scanf("%d%d",&n,&m) && (n+m))
    {
        memset(a,0,sizeof(a));
        equ = m;
        var = n;
        for(int i = 0; i < m; i++)
        {
            int k;
            scanf("%d%s%s",&k,s1,s2);
            a[i][var] = ((sts(s2)-sts(s1)+1)%7 + 7)%7;

            for(int j = 0; j < k; j++){
                int tp;
                scanf("%d",&tp);
                tp--;
                a[i][tp]++;
                a[i][tp]%=7;
            }
        }
        int freeNum = Gauss(equ,var);
        if(freeNum == -1)
        {
            printf("Inconsistent data.\n");
        }
        else if(freeNum > 0)
        {
            printf("Multiple solutions.\n");
        }
        else if(freeNum == 0)
        {
            for(int i = 0; i < var; i++){
                if(x[i] <= 2) printf("%d ",x[i]+7);
                else printf("%d ",x[i]);
            }
            printf("\n");
        }
    }
    return 0;
}