[ACM] POJ 2947 Widget Factory (高斯消元）

Widget Factory

Time Limit: 7000MS	Memory Limit: 65536K
Total Submissions: 4436	Accepted: 1502

Description

The widget factory produces several different kinds of widgets. Each widget is carefully built by a skilled widgeteer. The time required to build a widget depends on its type: the simple widgets need only 3 days, but the most complex ones may need as many as 9 days.

The factory is currently in a state of complete chaos: recently, the factory has been bought by a new owner, and the new director has fired almost everyone. The new staff know almost nothing about building widgets, and it seems that no one remembers how many days are required to build each diofferent type of widget. This is very embarrassing when a client orders widgets and the factory cannot tell the client how many days are needed to produce the required goods. Fortunately, there are records that say for each widgeteer the date when he started working at the factory, the date when he was fired and what types of widgets he built. The problem is that the record does not say the exact date of starting and leaving the job, only the day of the week. Nevertheless, even this information might be helpful in certain cases: for example, if a widgeteer started working on a Tuesday, built a Type 41 widget, and was fired on a Friday,then we know that it takes 4 days to build a Type 41 widget. Your task is to figure out from these records (if possible) the number of days that are required to build the different types of widgets.

Input

The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 300 of the different types, and the number 1 ≤ m ≤ 300 of the records. This line is followed by a description of the m records. Each record is described by two lines. The first line contains the total number 1 ≤ k ≤ 10000 of widgets built by this widgeteer, followed by the day of week when he/she started working and the day of the week he/she was fired. The days of the week are given bythe strings `MON', `TUE', `WED', `THU', `FRI', `SAT' and `SUN'. The second line contains k integers separated by spaces. These numbers are between 1 and n , and they describe the diofferent types of widgets that the widgeteer built. For example, the following two lines mean that the widgeteer started working on a Wednesday, built a Type 13 widget, a Type 18 widget, a Type 1 widget, again a Type 13 widget,and was fired on a Sunday.

4 WED SUN

13 18 1 13

Note that the widgeteers work 7 days a week, and they were working on every day between their first and last day at the factory (if you like weekends and holidays, then do not become a widgeteer!).

The input is terminated by a test case with n = m = 0 .

Output

For each test case, you have to output a single line containing n integers separated by spaces: the number of days required to build the different types of widgets. There should be no space before the first number or after the last number, and there should be exactly one space between two numbers. If there is more than one possible solution for the problem, then write `Multiple solutions.' (without the quotes). If you are sure that there is no solution consistent with the input, then write `Inconsistent data.'(without the quotes).

Sample Input

2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2
10 2
1 MON TUE 
3
1 MON WED
3
0 0

Sample Output

8 3
Inconsistent data.

Hint

Huge input file, 'scanf' recommended to avoid TLE.

Source

Central Europe 2005 解題思路：

被這個題意弄得真的無語了，讀了N遍.......

公司被吞并，老員工幾乎全部被炒鱿魚。一共有n種不同的工具，編号1-N（代碼中是0—N-1），每種工具的加工時間為3—9天，但是現在老員工不在我們不知道每種工具的加工時間，慶幸的是還保留着一些對勞工制造工具的記錄，對于每個老員工，他的記錄包括，他開始工作的時間（在某個星期的星期幾），被炒鱿魚的時間（某個星期的星期幾），在第幾個星期不知道.....在這段時間裡，他正好加工了k件物品，給出了這k件物品的編号。我們要做的就是通過這些記錄，來确定每種工具的加工時間是多少。

思路為建立線性方程組（涉及到了取模）:

對于每個記錄，建立一個方程，所有的記錄，建立為如下的方程：

（a[0][0]*X0 + a[0][1] *X1 + a[0][2]*X2+...........a[0][n-1]*Xn-1 ) %7= a[0][n]

（a[1][0]*X0 + a[1][1] *X1 + a[1][2]*X2+...........a[1][n-1]*Xn-1 ) %7= a[1][n]

................................................................................................................................

（a[m-1][0]*X0 + a[m-1][1] *X1 + a[m-1][2]*X2+...........a[m-1][n-1]*Xn-1 ) %7= a[m-1][n]

如上方程組，表示的是一共有m個記錄，即有m個方程，有n個變量（表示n個物品，編号0-N-1），方程中的x0, x1, x2........xn-1，代表的是第i種工具加工需要多長時間

a[ i ] [ j ] (0<=j<=n-1) ，表示第i個方程中（i從0開始）,編号為j的物品，加工的個數，即Xj, a[i][n] ，表示第i個方程中，加工完所有種類的工具，需要的時間，因為不知道開始時間和結束時間是在第幾個星期，隻知道星期幾，是以有 %7.

以樣例中的例子，來說一下方程組的建立.

2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2

初始化，增廣矩陣a[][]初始化為0.

樣例中 2 3 代表有一共兩種工具（編号0,1）, 3個勞工的記錄。

第一個勞工的記錄為 2 表示他加工了兩個工具，開始時間是 MON,表示星期一，結束時間為THU，表示星期四，下一行的1,2表示，他加工兩個工具，這兩個工具的編号，1,2（代碼中是 0，1）

這樣建立的方程為 (1* X0+ 1 *X2 )%7= ((4-1)%7+7)%7 ,方程後邊得是正整數.

第二個勞工的記錄為3 表示他加工了三個工具，開始時間為 MON，表示星期一，結束時間為FRI，表示星期五，下一行的1,1,2表示，他加工的三個工具裡面，編号分别是1,1,2，也就是第一種工具加工了兩個，第二種工具加工了1個。

這樣建立的方程為（2*X0+1*X2）%7=((5-1)%7+7)%7,

依次類推，

第三個勞工的記錄建立的方程為 (1*X0+2*X2) %7 =((7-1)%7+7)%7.

我們要做的就是根據這三個方程，把x0,x1，解出來。

當沒有解時，輸出 Inconsistent data. 無窮解時輸出 Multiple solutions. ，否則輸出每種工具的加工時間...

這種題目需要把模闆修改一下...一上午就研究了個模闆是怎麼回事....

代碼：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
using namespace std;
const int maxn = 310;
int equ, var; // 有equ個方程，var個變元。增廣陣行數為equ, 分别為0到equ - 1，列數為var + 1，分别為0到var.
int a[maxn][maxn];//增廣矩陣
int x[maxn]; // 解集.
int free_num;


inline int gcd(int a, int b)
{
    int t;
    while(b!=0)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}

inline int lcm(int a, int b)
{
    return a*b/gcd(a,b);
}
// 高斯消元法解方程組(Gauss-Jordan elimination).(-2表示有浮點數解，但無整數解，-1表示無解，0表示唯一解，大于0表示無窮解，并傳回自由變元的個數)
int change(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  return 7;
}
int Gauss(void)
{
    int i,j,k;
    int max_r; // 目前這列絕對值最大的行.
    int col; // 目前處理的列.
    int ta, tb;
    int LCM;
    int temp;
    // 轉換為階梯陣.
    col = 0; // 目前處理的列.
    for (k = 0; k < equ && col < var; k++, col++)
    { // 枚舉目前處理的行.
        // 找到該col列元素絕對值最大的那行與第k行交換.(為了在除法時減小誤差)
        max_r = k;
        for (i = k + 1; i < equ; i++)
        {
            if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i;
        }
        if (max_r != k)
        { // 與第k行交換.
            for (j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);
        }
        if (a[k][col] == 0)
        { // 說明該col列第k行以下全是0了，則處理目前行的下一列.
            k--;
            continue;
        }
        for (i = k + 1; i < equ; i++)
        { // 枚舉要删去的行.
            if (a[i][col] != 0)
            {
                LCM = lcm(abs(a[i][col]), abs(a[k][col]));
                ta = LCM / abs(a[i][col]), tb = LCM / abs(a[k][col]);
                if (a[i][col] * a[k][col] < 0) tb = -tb; // 異号的情況是兩個數相加.
                for (j = col; j < var + 1; j++)
                {
                    a[i][j] =(((a[i][j] * ta - a[k][j] * tb)%7+7)%7);
                }
            }
        }
    }
    //Debug();
    // 1. 無解的情況: 化簡的增廣陣中存在(0, 0, ..., a)這樣的行(a != 0).
    for (i = k; i < equ; i++)
    { // 對于無窮解來說，如果要判斷哪些是自由變元，那麼初等行變換中的交換就會影響，則要記錄交換.
        if (a[i][col] != 0) return -1;
    }
    // 2. 無窮解的情況: 在var * (var + 1)的增廣陣中出現(0, 0, ..., 0)這樣的行，即說明沒有形成嚴格的上三角陣.
    // 且出現的行數即為自由變元的個數.
    if (k < var)
        return var - k; // 自由變元有var - k個.
    // 3. 唯一解的情況: 在var * (var + 1)的增廣陣中形成嚴格的上三角陣.
    // 計算出Xn-1, Xn-2 ... X0.
    for (i = var - 1; i >= 0; i--)
    {
        temp = a[i][var];//等式右邊的數
        for (j = i + 1; j < var; j++)
        {
            if (a[i][j] != 0) temp -= a[i][j] * x[j];//把已知的解帶入，減去，隻剩下，一個未知的解
            temp=(temp%7+7)%7;
        }
        while(temp%a[i][i]!=0)//外層每次循環都是為了求 a[i][i],因為它是每個方程中唯一一個未知的變量（求該方程時）
            temp+=7;//因為天數不确定，而a[i][i]必須得為整數才可以，周期為7
        x[i]=(temp/a[i][i])%7;
    }
    return 0;
}

int main(void)
{
    int n,m,k,num;
    char s[5],e[5];
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {
        memset(a,0,sizeof(a));
        for(int i=0;i<m;i++)
        {
            scanf("%d",&k);
            scanf("%s%s",s,e);
            a[i][n]=((change(e)-change(s)+1)%7+7)%7;
            for(int j=1;j<=k;j++)//k是他打造的數量
            {
                scanf("%d",&num);//可能是相同的數
                num--;
                a[i][num]++;//系數++
                a[i][num]%=7;//有重複的。
            }
        }
        equ=m;//有m個方程
        var=n;//有多少個變量
        free_num = Gauss();
        if(free_num==0)
        {
            for(int i=0;i<n;i++)//根據題意，每個零件的加工時間在3-9天.
                if(x[i]<=2)
                x[i]+=7;
            for(int i=0;i<n-1;i++)
             cout<<x[i]<<" ";
            cout<<x[n-1]<<endl;
        }
        else if(free_num==-1)
            cout<<"Inconsistent data."<<endl;
        else
            cout<<"Multiple solutions."<<endl;
    }
    return 0;
}

參考：http://blog.csdn.net/duanxian0621/article/details/7408887

高斯消元法，是線性代數中的一個算法，可用來求解線性方程組，并可以求出矩陣的秩，以及求出可逆方陣的逆矩陣。

高斯消元法的原理是：

若用初等行變換将增廣矩陣化為，則AX = B與CX = D是同解方程組。

是以我們可以用初等行變換把增廣矩陣轉換為行階梯陣，然後回代求出方程的解。

以上是線性代數課的回顧，下面來說說高斯消元法在程式設計中的應用。

首先，先介紹程式中高斯消元法的步驟：

(我們設方程組中方程的個數為equ，變元的個數為var，注意：一般情況下是n個方程，n個變元，但是有些題目就故意讓方程數與變元數不同)

1. 把方程組轉換成增廣矩陣。

2. 利用初等行變換來把增廣矩陣轉換成行階梯陣。

枚舉k從0到equ – 1，目前處理的列為col(初始為0) ，每次找第k行以下(包括第k行)，col列中元素絕對值最大的列與第k行交換。如果col列中的元素全為0，那麼則處理col + 1列，k不變。

3. 轉換為行階梯陣，判斷解的情況。

① 無解

當方程中出現(0, 0, …, 0, a)的形式，且a != 0時，說明是無解的。

② 唯一解

條件是k = equ，即行階梯陣形成了嚴格的上三角陣。利用回代逐一求出解集。

③ 無窮解。

條件是k < equ，即不能形成嚴格的上三角形，自由變元的個數即為equ – k，但有些題目要求判斷哪些變元是不缺定的。

這裡單獨介紹下這種解法：

首先，自由變元有var - k個，即不确定的變元至少有var - k個。我們先把所有的變元視為不确定的。在每個方程中判斷不确定變元的個數，如果大于1個，則該方程無法求解。如果隻有1個變元，那麼該變元即可求出，即為确定變元。

以上介紹的是求解整數線性方程組的求法，複雜度是O(n3)。浮點數線性方程組的求法類似，但是要在判斷是否為0時，加入EPS，以消除精度問題。

下面講解幾道OJ上的高斯消元法求解線性方程組的題目：

POJ 1222 EXTENDED LIGHTS OUT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1222

POJ 1681 Painter's Problem

http://acm.pku.edu.cn/JudgeOnline/problem?id=1681

POJ 1753 Flip Game

http://acm.pku.edu.cn/JudgeOnline/problem?id=1753

POJ 1830 開關問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=1830

POJ 3185 The Water Bowls

http://acm.pku.edu.cn/JudgeOnline/problem?id=3185

開關窗戶，開關燈問題，很典型的求解線性方程組的問題。方程數和變量數均為行數*列數，直接套模闆求解即可。但是，當出現無窮解時，需要枚舉解的情況，因為無法判斷哪種解是題目要求最優的。

POJ 2947 Widget Factory

http://acm.pku.edu.cn/JudgeOnline/problem?id=2947

求解同餘方程組問題。與一般求解線性方程組的問題類似，隻要在求解過程中加入取餘即可。

注意：當方程組唯一解時，求解過程中要保證解在[3, 9]之間。

POJ 1166 The Clocks

http://acm.pku.edu.cn/JudgeOnline/problem?id=1166

經典的BFS問題，有各種解法，也可以用逆矩陣進行矩陣相乘。

但是這道題用高斯消元法解決好像有些問題(困擾了我N天...持續困擾中...)，由于周期4不是素數，故在求解過程中不能進行取餘(因為取餘可能導緻解集變大)，但最後求解集時，還是需要進行取餘操作，那麼就不能保證最後求出的解是正确的...在discuss裡提問了好幾天也沒人回答...希望哪位路過的大牛指點下～～

POJ 2065 SETI

http://acm.pku.edu.cn/JudgeOnline/problem?id=2065

同樣是求解同餘方程組問題，由于題目中的p是素數，可以直接在求解時取餘，套用模闆求解即可。(雖然AC的人很少，但它還是比較水的一道題，)

POJ 1487 Single-Player Games

http://acm.pku.edu.cn/JudgeOnline/problem?id=1487

很麻煩的一道題目...題目中的叙述貌似用到了編譯原理中的詞法定義(看了就給人不想做的感覺...)

解方程組的思想還是很好看出來了(前提是通讀題目不下5遍...)，但如果把樹的字元串表達式轉換成方程組是個難點，我是用棧 + 遞歸的做法分解的。首先用棧的思想求出該結點的孩子數，然後遞歸分别求解各個孩子。

這題解方程組也與衆不同...首先是求解浮點數方程組，要注意精度問題，然後又詢問不确定的變元，按前面說的方法求解。

一頓折騰後，這題居然寫了6000+B...而且囧的是巨人C++ WA，G++ AC，可能還是精度的問題吧...看這題目，看這代碼，就沒有改的欲望...

hdu OJ 2449

http://acm.hdu.edu.cn/showproblem.php?pid=2449

哈爾濱現場賽的一道純高斯題，當時鶴牛敲了1個多小時...主要就是寫一個分數類，套個高精模闆(偷懶點就Java...)搞定～～

注意下0和負數時的輸出即可。

fze OJ 1704

http://acm.fzu.edu.cn/problem.php?pid=1704

福大月賽的一道題目，還是經典的開關問題，但是方程數和變元數不同(考驗模闆的時候到了～～)，最後要求增廣陣的階，要用到高精度～～

Sgu 275 To xor or not to xor

http://acm.sgu.ru/problem.php?contest=0&problem=275

題解:

http://hi.baidu.com/czyuan%5Facm/blog/item/be3403d32549633d970a16ee.html

模闆：

//高斯消元模闆
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <cmath>
using namespace std;
const int maxn=105;
int equ,var; // 有equ個方程，var個變元。增廣陣行數為equ, 分别為0到equ - 1，列數為var + 1，分别為0到var.
int a[maxn][maxn];
int x[maxn]; // 解集.
bool free_x[maxn]; // 判斷是否是不确定的變元.
int free_num;
void Debug(void)
{
    int i,j;
    for(i=0;i<equ;i++)
    {
        for(j=0;j<var+1;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
inline int gcd(int a, int b)
{
    int t;
    while (b!=0)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}
inline int lcm(int a, int b)
{
    return a*b/gcd(a,b);
}
// 高斯消元法解方程組(Gauss-Jordan elimination).(-2表示有浮點數解，但無整數解，-1表示無解，0表示唯一解，大于0表示無窮解，并傳回自由變元的個數)
int Gauss(void)
{
    int i,j,k;
    int max_r; // 目前這列絕對值最大的行.
    int col; // 目前處理的列.
    int ta,tb;
    int LCM;
    int temp;
    int free_x_num;
    int free_index;
    // 轉換為階梯陣.
    col=0; // 目前處理的列.
    for(k=0;k<equ&&col<var;k++,col++)
    { // 枚舉目前處理的行.
        // 找到該col列元素絕對值最大的那行與第k行交換.(為了在除法時減小誤差)
        max_r=k;
        for(i=k+1;i<equ;i++)
        {
            if(abs(a[i][col])>abs(a[max_r][col]))
                max_r=i;
        }
        if(max_r!=k)
        { // 與第k行交換.
            for(j=k;j<var+1;j++)
                swap(a[k][j],a[max_r][j]);
        }
        if(a[k][col]==0)
        { // 說明該col列第k行以下全是0了，則處理目前行的下一列.
            k--; continue;
        }
        for(i=k+1;i<equ;i++)
        { // 枚舉要删去的行.
            if (a[i][col]!=0)
            {
                LCM=lcm(abs(a[i][col]),abs(a[k][col]));
                ta=LCM/abs(a[i][col]),tb=LCM/abs(a[k][col]);
                if(a[i][col]*a[k][col]<0) tb=-tb; // 異号的情況是兩個數相加.
                for(j=col;j<var+1;j++)
                {
                    a[i][j]=a[i][j]*ta-a[k][j]*tb;
                }
            }
        }
    }
    //Debug();
    // 1. 無解的情況: 化簡的增廣陣中存在(0, 0, ..., a)這樣的行(a != 0).
    for(i=k;i<equ;i++)
    { // 對于無窮解來說，如果要判斷哪些是自由變元，那麼初等行變換中的交換就會影響，則要記錄交換.
        if (a[i][col]!=0)
            return -1;
    }
    // 2. 無窮解的情況: 在var * (var + 1)的增廣陣中出現(0, 0, ..., 0)這樣的行，即說明沒有形成嚴格的上三角陣.
    // 且出現的行數即為自由變元的個數.
    if(k<var)
    {
        // 首先，自由變元有var - k個，即不确定的變元至少有var - k個.
        for (i=k-1;i>=0;i--)
        {
            // 第i行一定不會是(0, 0, ..., 0)的情況，因為這樣的行是在第k行到第equ行.
            // 同樣，第i行一定不會是(0, 0, ..., a), a != 0的情況，這樣的無解的.
            free_x_num=0; // 用于判斷該行中的不确定的變元的個數，如果超過1個，則無法求解，它們仍然為不确定的變元.
            for(j=0;j<var;j++)
            {
                if(a[i][j]!=0&&free_x[j])
                    free_x_num++,free_index = j;
            }
            if(free_x_num>1)
                continue; // 無法求解出确定的變元.
            // 說明就隻有一個不确定的變元free_index，那麼可以求解出該變元，且該變元是确定的.
            temp=a[i][var];
            for(j=0;j<var;j++)
            {
                if(a[i][j]!=0&&j!=free_index)
                temp-=a[i][j]*x[j];
            }
            x[free_index]=temp/a[i][free_index]; // 求出該變元.
            free_x[free_index]=0; // 該變元是确定的.
        }
        return var-k; // 自由變元有var - k個.
    }
    // 3. 唯一解的情況: 在var * (var + 1)的增廣陣中形成嚴格的上三角陣.
    // 計算出Xn-1, Xn-2 ... X0.
    for (i=var-1;i>=0;i--)
    {
        temp=a[i][var];
        for(j=i+1;j<var;j++)
        {
            if(a[i][j]!=0) 
                temp-=a[i][j]*x[j];
        }
        if(temp%a[i][i]!=0) 
            return -2; // 說明有浮點數解，但無整數解.
        x[i]=temp/a[i][i];
    }
    return 0;
}
int main(void)
{
    int i, j;
    while (scanf("%d %d",&equ,&var)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        memset(free_x,1,sizeof(free_x)); // 一開始全是不确定的變元
        
        for(i=0;i<equ;i++)//構造增廣矩陣
            for(j=0;j<var+1;j++)
                scanf("%d",&a[i][j]);
//        Debug();
        free_num=Gauss();
        if(free_num==-1) printf("無解!\n");
        else if(free_num==-2) printf("有浮點數解，無整數解!\n");
        else if(free_num>0)
        {
            printf("無窮多解! 自由變元個數為%d\n",free_num);
            for(i=0;i<var;i++)
            {
                if(free_x[i]) printf("x%d 是不确定的\n",i+1);
                else printf("x%d: %d\n",i+1,x[i]);
            }
        }
        else
        {
            for(i=0;i<var;i++)
                printf("x%d: %d\n",i+1,x[i]);
        }
        printf("\n");
    }
    return 0;
}