poj 2947 Widget Factory

Widget Factory

題意:有n件裝飾品，有m組信息。(1 <= n ,m<= 300)每組信息有開始的星期和結束的星期(是在mod 7範圍內的)並且還包括num種裝飾品的種類(1~n)，其中每種裝飾品所用的時間3 <= x[i] <= 9;種類的輸入可以重覆；

思路:

1.根據輸入建立增廣矩陣a[][],但是在建立和求解的過程中由於是mod意義下的，所以輸入的個數和最終所用的時間都要mod 7;(分析可知當個數是7的同餘類時，開始星期相同則結束星期也相同)

2.前面幾個高斯消元，我用的是free_var來判斷是否有自由變元，這是在輸入的方程數和求解變元數相等的情況才成立。在本題中對於sample 1就會發現方程數原本就比變元多1，這時計算出的free_var = 1，但是並不是將就有了一個維度的自由變元。還是要看有用方程的個數row與var之間的關係；

3.在得到上三角陣求解變元x[i]的時候，需要解一個模線性方程，a[i][i]*x[i] + 7*y = ret(mod 7)；ret為a[i][col]用已知的x[j]消去除a[i][i]得到的；

這時調用exgcd()即可求解；最後註意解要在3~9範圍內即可；

ps:時間性能不是很好，竟然用了1704ms...最短的是297ms..差距啊！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
int a[305][305];
int equ,var;
int x[305];
const int MOD = 7;
template <typename T>
T abs(T a){return a < 0 ? -a:a;}
void debug()
{
    puts("********");
    int i,j;
    rep0(i,0,equ){
        rep1(j,0,var)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }puts("********");
}
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;
}
void exgcd(int a,int b,int& d,int& x,int& y)
{
    if(!b){d = a;x = 1;y = 0;}
    else{
        exgcd(b,a%b,d,y,x);
        y -= x*(a/b);
    }
}
int Guass()
{
    int i,j,k,free_var = 0,row,col;
    for(row = 0,col = 0;row < equ && col < var;row++,col++){
        int mx = row;
        rep0(j,row+1,equ)
            if(abs(a[j][col]) > abs(a[mx][col]))  mx = j;
        if(a[mx][col] == 0){
            row--;  // 行不變；不能通過這裡記錄自由變元的個數，只能記錄沒用的col
            continue;
        }
        if(mx != row)
            rep1(k,col,var)
                swap(a[row][k],a[mx][k]);
        rep0(j,row+1,equ){
            if(a[j][col]){
                int lcm = LCM(abs(a[row][col]),abs(a[j][col]));
                int ration_row = lcm/abs(a[row][col]),ration_j = lcm/abs(a[j][col]);
                if(a[row][col]*a[j][col] < 0) ration_row = -ration_row; //符號相反變加法；
                rep1(k,col,var)
                    a[j][k] = (a[j][k]*ration_j - a[row][k]*ration_row)%7;
            }
        }
    }
    //debug();
    rep0(i,row,equ)
        if(a[i][var] != 0) return -1;    //無解
    if(row < var) return var - row;//row表示有用的方程數方程,但是要在判斷出有解的前提下才能說有多組解；
    rep_1(i,var - 1,0){  // ***若為唯一解，其實就是var維方陣
        int ret = a[i][var];
        for(j = i+1;j < var;j++) //利用已求得的變元消去第row行col後面的元素，得到一元方程；
            ret -= x[j]*a[i][j];
        ret = ((ret%7)+7)%7;
        int d,x1,y;
        //構造出 a[i][i]*x[i] + 7*y = ret(mod 7);且gcd(a[row][col],7) = 1)因為a[row][col] != 0
        if(a[i][i] < 0) a[i][i] = -a[i][i],ret = -ret;
        exgcd(a[i][i],7,d,x1,y); //之後乘上ret弄到3~9範圍即可；
        x[i] = ((ret*x1)%7+7)%7;
        if(x[i] < 3)   x[i] += 7;
    }
    return 0;
}
const char str[7][5] = {{"MON"},{"TUE"},{"WED"},{"THU"},{"FRI"},{"SAT"},{"SUN"}};
int date_id(char *c)
{
    for(int i = 0;i < 7;i++)
        if(strcmp(str[i],c) == 0) return i;
}
int main()
{
    int i,j,n,m;
    char s[5],t[5];
    while(scanf("%d%d",&n,&m) == 2 && n + m){
        MS0(a);
        equ = m;var = n;
        int kind,num;
        rep0(i,0,m){
            scanf("%d%s%s",&num,s,t);
            a[i][var] = date_id(t)-date_id(s)+1;
            if(a[i][var] < 0) a[i][var] += 7;
            rep0(j,0,num){
                scanf("%d",&kind);
                a[i][--kind]++;
            }
            rep1(j,0,var) a[i][j] %= 7;
        }
        //debug();
        int ret = Guass();
        if(ret == -1) puts("Inconsistent data.");
        else if(ret > 0) puts("Multiple solutions.");
        else{
            rep0(i,0,var)
                printf("%d%c",x[i],i == var - 1?'\n':' ');
        }
    }
    return 0;
}