首页 > 代码库 > POJ 2947 Widget Factory （高斯消元 判多解 无解 和解集 模7情况）
POJ 2947 Widget Factory （高斯消元 判多解 无解 和解集 模7情况）
题目链接
题意:
公司被吞并，老员工几乎全部被炒鱿鱼。一共有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.
然后处理一下列方程就行了。a[i][n] = 每个记录 的时间。
在做的过程中会遇到一些问题，可以参见注释，还有我的模板中加上那个判断有浮点数解的地方返回-2，会不对，貌似不应该加，这道题应该只有整数解。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 300+10; 9 const int INF = 1<<28; 10 using namespace std; 11 int equ, var, fn; 12 int a[maxn][maxn], x[maxn]; 13 bool free_x[maxn]; 14 15 int gcd(int a, int b) 16 { 17 return b==0?a:gcd(b, a%b); 18 } 19 int lcm(int a, int b) 20 { 21 return a*b/gcd(a, b); 22 } 23 int Gauss() 24 { 25 int x_mo; 26 x_mo = 7; 27 int i, j, k, max_r, col; 28 int ta, tb, LCM, tmp, fx_num; 29 int free_index; 30 col = 0; 31 32 for(k = 0; k<equ && col<var; k++, col++) 33 { 34 max_r = k; 35 for(i = k+1; i < equ; i++) 36 if(abs(a[i][col])>abs(a[max_r][col])) 37 max_r = i; 38 39 if(max_r != k) 40 for(j = k; j < var+1; j++) 41 swap(a[k][j], a[max_r][j]); 42 43 if(a[k][col]==0) 44 { 45 k--; 46 continue; 47 } 48 for(i = k+1; i < equ; i++) 49 { 50 if(a[i][col] != 0) 51 { 52 LCM = lcm(abs(a[i][col]), abs(a[k][col])); 53 ta = LCM/abs(a[i][col]); 54 tb= LCM/abs(a[k][col]); 55 if(a[i][col]*a[k][col] < 0) tb = -tb; 56 57 for(j = col; j < var+1; j++) 58 a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%x_mo+x_mo)%x_mo; 59 } 60 } 61 } 62 for(i = k; i < equ; i++) 63 if(a[i][col] != 0) 64 return -1; 65 66 if(k < var) 67 return var-k; 68 69 for(i = var-1; i >= 0; i--) 70 { 71 tmp = a[i][var]; 72 for(j = i+1; j < var; j++) 73 if(a[i][j] != 0) 74 tmp = ((tmp-a[i][j]*x[j])%x_mo+x_mo)%x_mo; 75 76 if(a[i][i]==0) 77 x[i] = 0; 78 else 79 { 80 //if(tmp%a[i][i] != 0) return -2; 81 while(tmp%a[i][i]!=0) tmp += x_mo; 82 x[i] = (tmp/a[i][i])%x_mo; 83 } 84 } 85 return 0; 86 } 87 int check(char s[]) 88 { 89 if(strcmp(s,"MON")==0) return 1; 90 else if(strcmp(s,"TUE")==0) return 2; 91 else if(strcmp(s,"WED")==0) return 3; 92 else if(strcmp(s,"THU")==0) return 4; 93 else if(strcmp(s,"FRI")==0) return 5; 94 else if(strcmp(s,"SAT")==0) return 6; 95 else return 7; 96 } 97 int main() 98 { 99 int n, m, i, k;100 char s1[20], s2[20];101 while(~scanf("%d%d", &n, &m))102 {103 equ = m; var = n; //m个方程，n个未知数104 if(n==0&&m==0) break;105 memset(a, 0, sizeof(a));106 memset(x, 0, sizeof(x));107 memset(free_x, -1, sizeof(free_x));108 for(i = 0; i < m; i++)109 {110 scanf("%d", &k);111 getchar();112 scanf("%s %s", s1, s2);113 a[i][n] = ((check(s2)-check(s1)+1)%7+7)%7; //s1s2顺序不能乱，而且因为有负的所以需要这样处理114 while(k--)115 {116 int tmp;117 scanf("%d", &tmp);118 tmp --; //因为a里面是从0开始的119 a[i][tmp] ++;120 a[i][tmp] %= 7; //一定要对7取余，不然会wa,大概因为上面a[i][n]取余了，如果这里不取余会使方程无解吧。121 }122 }123 fn = Gauss();124 if(fn<0)125 printf("Inconsistent data.\n");126 if(fn>0)127 printf("Multiple solutions.\n");128 else if(fn==0)129 {130 for(i = 0; i < n; i++)131 {132 if(x[i]<=2) x[i] += 7; //注意题目说3——9天133 if(i==n-1)134 printf("%d\n", x[i]);135 else136 printf("%d ", x[i]);137 }138 }139 }140 return 0;141 }