POJ 2947 Widget Factory(高斯消元)

题目连接～～～
 　　本题是对同余方程组消元，方程比较好列，本题可以列m个方程，每个方程可以列成k1*x1 + k2*x2……kn*xn = y1 (mod 7)
 y1是加工这一批零件所需要的时间。然后解方程就可以了。

代码：

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <cstdlib>
     
    
   

    

     

    
    

     

      #include <cmath>
     
    
   

    

     

    
    

     

      #include <ctime>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define INF 0x3f3f3f3f
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const int MX = 300 + 10 ;
     
    
   

    

     

    
    

     

      const int MY = 100 + 10 ;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int g[MX][MX] ,ans[MX] ;
     
    
   

    

     

    
    

     

      int Solve(char s[]){
     
    
   

    

     

    
    

     
 int f_num = 0 ;
     
    
   

    

     

    
    

     
 if(strcmp(s ,"MON") == 0) f_num = 1 ;
     
    
   

    

     

    
    

     
 else if(strcmp(s ,"TUE") == 0) f_num = 2 ;
     
    
   

    

     

    
    

     
 else if(strcmp(s ,"WED") == 0) f_num = 3 ;
     
    
   

    

     

    
    

     
 else if(strcmp(s ,"THU") == 0) f_num = 4 ;
     
    
   

    

     

    
    

     
 else if(strcmp(s ,"FRI") == 0) f_num = 5 ;
     
    
   

    

     

    
    

     
 else if(strcmp(s ,"SAT") == 0) f_num = 6 ;
     
    
   

    

     

    
    

     
 else if(strcmp(s ,"SUN") == 0) f_num = 7 ;
     
    
   

    

     

    
    

     
 return f_num ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Gcd(int a ,int b){
     
    
   

    

     

    
    

     
 int tmp ;
     
    
   

    

     

    
    

     
 while(b){
     
    
   

    

     

    
    

     

       tmp = a ;
     
    
   

    

     

    
    

     

       a = b ;
     
    
   

    

     

    
    

     

       b = tmp % b ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return a ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Lcm(int a ,int b){
     
    
   

    

     

    
    

     
 return a/Gcd(a ,b)*b ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Gauss(int n ,int m ,int g[][MX] ,int mod){//n行 m列
     
    
   

    

     

    
    

     
 int max_r ;
     
    
   

    

     

    
    

     
 int k = 0 ,col = 0 ;
     
    
   

    

     

    
    

     
 for( ;k < n && col < m ; ++k ,++col){
     
    
   

    

     

    
    

     

       max_r = k ;
     
    
   

    

     

    
    

     
 for(int i = k+1 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 if(abs(g[max_r][col])  < abs(g[i][col]))
     
    
   

    

     

    
    

     

       max_r = i ;
     
    
   

    

     

    
    

     
 if(!g[max_r][col]){
     
    
   

    

     

    
    

     

       k-- ; continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(max_r != k){
     
    
   

    

     

    
    

     
 for(int i = col ;i <= m ; ++i)
     
    
   

    

     

    
    

     

       swap(g[k][i] ,g[max_r][i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = k + 1 ;i < n ; ++i){
     
    
   

    

     

    
    

     
 if(g[i][col]){
     
    
   

    

     

    
    

     
 int LCM = Lcm(abs(g[k][col]) ,abs(g[i][col])) ;
     
    
   

    

     

    
    

     
 int ta = LCM/abs(g[i][col]) ;
     
    
   

    

     

    
    

     
 int tb = LCM/abs(g[k][col]) ;
     
    
   

    

     

    
    

     
 if(g[i][col] * g[k][col] < 0) tb = -tb ;
     
    
   

    

     

    
    

     
 for(int j = col ;j <= m ; ++j)
     
    
   

    

     

    
    

     

       g[i][j] = ((g[i][j]*ta - g[k][j]*tb)%mod +mod)%mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = k ;i < n ; ++i)
     
    
   

    

     

    
    

     
 if(g[i][col]) return -1 ;
     
    
   

    

     

    
    

     
 if(k < m) return m-k ;
     
    
   

    

     

    
    

     
 for(int i = n-1 ;i >= 0 ; --i){
     
    
   

    

     

    
    

     
 int tmp = g[i][m] ;
     
    
   

    

     

    
    

     
 for(int j = i+1 ;j < m ; ++j){
     
    
   

    

     

    
    

     

       tmp -= g[i][j]*ans[j] ;
     
    
   

    

     

    
    

     

       tmp = (tmp%mod + mod)%mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int sum ;
     
    
   

    

     

    
    

     
 for(int t = 3 ;t <= 9 ; ++t){
     
    
   

    

     

    
    

     

       sum = ((g[i][i]*t)%mod + mod)%mod ;
     
    
   

    

     

    
    

     
 if(sum == tmp){
     
    
   

    

     

    
    

     

       ans[i] = t ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 char s1[MX] ,s2[MX] ;
     
    
   

    

     

    
    

     
 int n ,m ,mod = 7 ,num ,tmp ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&m)){
     
    
   

    

     

    
    

     
 if(!n && !m) break ;
     
    
   

    

     

    
    

     
 memset(g ,0 ,sizeof(g)) ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < m ; ++i){
     
    
   

    

     

    
    

     
 scanf("%d%s%s" ,&num ,s1 ,s2) ;
     
    
   

    

     

    
    

     
 int d1 = Solve(s1) ;
     
    
   

    

     

    
    

     
 int d2 = Solve(s2) ;
     
    
   

    

     

    
    

     

       g[i][n] = ((d2 - d1 + mod)%mod + 1)%mod ;
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < num ; ++j){
     
    
   

    

     

    
    

     
 scanf("%d" ,&tmp) ;
     
    
   

    

     

    
    

     

       g[i][tmp-1] = (g[i][tmp-1]+1)%mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 memset(ans ,0 ,sizeof(ans)) ;
     
    
   

    

     

    
    

     
 int f_num = Gauss(m ,n ,g ,mod) ;
     
    
   

    

     

    
    

     
 if(!f_num) {
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 if(!i) printf("%d" ,ans[i]) ;
     
    
   

    

     

    
    

     
 else printf(" %d" ,ans[i]) ;
     
    
   

    

     

    
    

     
 puts("") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(f_num == -1) puts("Inconsistent data.") ;
     
    
   

    

     

    
    

     
 else puts("Multiple solutions.") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/52037223