poj 2947 Widget Factory(高斯消元模线性方程)

大致题意：产品制造者制造型号不同的产品所需的时间是不同的（规定为3~9天），现在已知生产产品的的种数N和工作者的人数M，告诉你每个工作者是从星期几开始工作，星期几结束的（可能隔着n周），这个工作者生产了K件产品，产品的型号分别是多少。根据以上信息，求是否可以求出这N中产品的具体生产所需时间(无解一解多解)，有解输出解，无解和多解输出相应信息。

Time Limit: 7000MSMemory Limit: 65536K

样例：

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.

思路：比较典型的求解线性方程组的解的题目,n种产品对应n个未知量,m个工作者对应m个方程，每个方程的解为(END_DAY - START_DAY + 1 +7) mod 7。这个题简单在对7取模，7是素数，每个模线性方程对应唯一解。所以如果对应的方程组有一解，则对应的模线性方程中的未知量也只有一解。方程组多解时，模线性方程也不可能出现无解的情况，所以也是多解，无解同理肯定对应无解。

高斯消元的几个步骤：1.选主元（选最大为主元以减少误差） 2.向下消元 3.根据方程组最后的形式判断解的情况（出现系数全为0最后一位非0的是无解，有多余全0行则多解，严格三角阵为一解）。判断解的顺序是：无解 - > 多解 - > 一解（非整数解 - > 整数解）

对于最后求模线性方程的解，由于答案就在3~9之间，枚举比较简单，扩展GCD和求乘法逆元都相对较麻烦。

最后注意矩阵进行累加，消项等运算时要时刻对7取模，否则容易超出范围。

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<cstring>
  4 const int MAXNUM=305;
  5 char date[7][5]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
  6 int fun[MAXNUM][MAXNUM];
  7 int res[MAXNUM];
  8 int n,m;
  9 int gcd(int a,int b){
 10     if(b==0){
 11         return a;
 12     }
 13     return gcd(b,a%b);
 14 }
 15 
 16 int lcm(int a,int b){
 17     return a*b/gcd(a,b);
 18 }
 19 int gauss(){
 20     int i,j,k,max,col=0;
 21     for(k=0;k<m&&col<n;k++,col++){　　//枚举第K行，第col列
 22         max=k;
 23         for(i=k+1;i<m;i++){　　//选第k行后的所有行中第col列最大的那一行做主元
 24             if(fabs(fun[i][col])>fabs(fun[max][col])){
 25                 max=i;
 26             }
 27         }
 28         if(max!=k){//交换行
 29             for(j=k;j<=n;j++){
 30                 int temp=fun[k][j];
 31                 fun[k][j]=fun[max][j];
 32                 fun[max][j]=temp;
 33             }
 34         }
 35         if(fun[k][col]==0){　　//如果第col列已经是0，那么继续枚举第k行第col+1列
 36             k--;
 37             continue;
 38         }
 39         for(i=k+1;i<m;i++){　　//向下消元
 40             if(fun[i][col]!=0){
 41                 int LCM=lcm(fun[i][col],fun[k][col]);
 42                 int ta=LCM/fun[i][col];
 43                 int tb=LCM/fun[k][col];
 44                 for(j=col;j<=n;j++){
 45                     fun[i][j]=((fun[i][j]*ta-fun[k][j]*tb)%7+7)%7;
 46                 }
 47             }
 48         }
 49     }
 50     for(i=k;i<m;i++){　　//判断无解
 51         if(fun[i][n]!=0)return -1;
 52     }
 53     if(k<n)return 0;　　//最后k的值是非自由元的个数，k<n为多解
 54     for(i=n-1;i>=0;i--){　　//一解时自下而上回带求解（上三角）
 55         for(j=i+1;j<n;j++){
 56             fun[i][n]=((fun[i][n]-fun[i][j]*res[j])%7+7)%7;
 57         }
 58         for(j=3;j<=9;j++){
 59             if((j*fun[i][i])%7==fun[i][n]){
 60                 res[i]=j;break;
 61             }
 62         }
 63     }
 64     return 1; 
 65 }
 66 int main(){
 67     int i,j,cnt,pos1,pos2,temp;
 68     char c1[5],c2[5];
 69     while(scanf("%d%d",&n,&m)&&(m||n)){
 70         memset(fun,0,sizeof(fun));
 71         for(j=0;j<m;j++){
 72             scanf("%d %s %s",&cnt,c1,c2);
 73             for(i=0;i<7;i++){
 74                 if(strcmp(c1,date[i])==0){
 75                     pos1=i;
 76                 }
 77                 if(strcmp(c2,date[i])==0){
 78                     pos2=i;
 79                 }
 80             }
 81             fun[j][n]=pos2-pos1+1+7;
 82             for(i=0;i<cnt;i++){
 83                 scanf("%d",&temp);
 84                 fun[j][temp-1]++;
 85             }
 86             for(i=0;i<=n;i++)fun[j][i]%=7;
 87         }
 88         int ans=gauss();
 89         if(ans==-1){
 90             printf("Inconsistent data.\n");
 91         }
 92         else if(ans==0){
 93             printf("Multiple solutions.\n");
 94         }
 95         else if(ans==1){
 96             
 97             for(i=0;i<n-1;i++){
 98                 printf("%d ",res[i]);
 99             }
100             printf("%d",res[n-1]);
101             printf("\n");
102         }
103     }
104     return 0;
105 }

poj 2947 Widget Factory(高斯消元 模线性方程)

poj 2947 Widget Factory(高斯消元模线性方程)