POJ 2947 Widget Factory (高斯消元解同余方程组)

题意：N种物品，M条记录，接写来M行，每行有K，str1，str2，表示第i个记录从星期str1到星期str2，做了K件物品，接下来的K个数为物品的编号。求做每个物品所需的时间，并且最后结果在3-9之间很容易想到高斯消元。但是是带同余方程的高斯消元，开始建立关系的时候就要MOD 7 解此类方程式时最后求解的过程要用到扩展gcd的思想，举个例子，如果最后得到的矩阵为： 1 1 4 0 6 4 则6 * X2 % 7= 4 % 7 则相当于6 * X2 + 7 * Y = 4，利用扩展gcd则可求出X2为3，则第一个方程为 X1 * 1 % 7 + 1*3 % 7 = 4 % 7 则相当于 X1 + 7 * Y = 1 得到X1=1；但其实这道题用扩展gcd真的大材小用了，因为模数是固定的而且很小就是7，所以直接枚举试就可以了~~

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long LL;

int gcd(int a, int b){
    return b ? gcd(b, a%b) : a;
}
int lcm(int a, int b){
    return a / gcd(a,b) * b;
}
const int MAX_EQU = 310;
typedef struct  equation_set{
    int equ, var;               	//方程个数、变元个数，则增广矩阵有equ行、var+1列.
    int mat[MAX_EQU][MAX_EQU+1];  	//增广矩阵
    int x[MAX_EQU];            	 	//方程解向量
    bool free_x[MAX_EQU];       	//判断是否是不确定变元

    void init(int in_equ, int in_var);
    void debug();
    int gauss();
}EQU;
void equation_set::init(int in_equ, int in_var){
    equ = in_equ;
    var = in_var;

    memset(mat, 0, sizeof(mat));
    memset(x, 0, sizeof(x));
    memset(free_x, 1, sizeof(free_x));
}
void equation_set::debug(){
    for (int i = 0; i < equ; i ++){
        for (int j = 0; j < var; j ++)
            cout << mat[i][j] << " ";
        cout << mat[i][var] << endl;
    }
}
int equation_set::gauss(){
    int row = 0, col = 0;
    int max_row;
    while (row < equ && col < var){
        max_row = row;
        for (int i = row + 1; i < equ; i ++)
            if (abs(mat[i][col]) > abs(mat[max_row][col]))
                max_row = i;
        if (max_row != row){
            for (int j = 0; j <= var; j ++){
                int tmp = mat[row][j];
                mat[row][j] = mat[max_row][j];
                mat[max_row][j] = tmp;
            }
        }
        if (mat[row][col] == 0){
            col ++;
            continue;
        }
		//普通方程组行阶梯化:
        for (int i = row + 1; i < equ; i ++){
            if (mat[i][col] != 0){
                int LCM = lcm(abs(mat[i][col]), abs(mat[row][col]));
                int ta = LCM  / abs(mat[i][col]), tb = LCM / abs(mat[row][col]);
                if (mat[i][col] * mat[row][col] < 0)    tb = -tb;
                for (int j = 0; j <= var; j ++)
                    mat[i][j] = ((mat[i][j] * ta - mat[row][j] * tb) % 7 + 7) % 7;
            }
        }

        row++, col++;
    }
    //debug();

    //1. 无解
    for (int i = row; i < equ; i++){
        if (mat[i][col] != 0) return -1;
    }
    //2.无穷解(这里只是计算出了确定变元，对于多解的计算，需要枚举自由变元的状态或者其他方法求解.)
    if (row < var){
        return 1;
    }
    //3.唯一解
    for (int i = row - 1; i >= 0; i --){
        int tmp = (mat[i][var] % 7 + 7) % 7;
        for (int j = var - 1; j > i; j --)
            tmp = ((tmp - x[j] * mat[i][j]) % 7 + 7) % 7;
        while(tmp % mat[i][i] != 0)
            tmp += 7;
        x[i] = (tmp / mat[i][i] % 7 + 7) % 7;
    }
    return 0;
}
int week(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;
}
int main(){
    int n,m;
    while(scanf("%d%d", &n, &m) == 2){
        if (n + m == 0)
            break;
        EQU E;
        E.init(m, n);
        for (int i = 0; i < m; i ++){
            int k;
            char s1[10], s2[10];
            scanf("%d", &k);
            scanf("%s%s", s1, s2);
            E.mat[i][n] = (week(s2) - week(s1) + 1) % 7;
            for (int j = 0; j < k; j ++){
                int tmp;
                scanf("%d", &tmp);
                E.mat[i][tmp-1] ++;
            }
            for (int j = 0; j < n; j ++)
                E.mat[i][j] %= 7;
        }
        //E.debug();
        int p = E.gauss();
        if (p == -1){
            printf("Inconsistent data.\n");
        }
        else if (p == 1){
            printf("Multiple solutions.\n");
        }
        else{
            for (int i = 0; i < n; i ++)
                if(E.x[i] < 3)
                    E.x[i] += 7;
            for (int i = 0; i < n - 1; i ++)
                printf("%d ", E.x[i]);
            printf("%d\n", E.x[n-1]);
        }
    }
	return 0;
}

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG