高斯消元法解方程组！！
不过这题要取模
高斯消元法详解请看这：http://blog.163.com/baobao_zhang@126/blog/static/4825236720099202538409/
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #include<map> 9 #define ll __int64 10 #define pi acos(-1.0) 11 #define MAX 500 12 using namespace std; 13 int equ,var; 14 int an[MAX][MAX]; 15 int x[MAX]; 16 bool free_x[MAX]; 17 int free_num; 18 map<string,int>p; 19 void init() 20 { 21 p["MON"] = 0; 22 p["TUE"] = 1; 23 p["WED"] = 2; 24 p["THU"] = 3; 25 p["FRI"] = 4; 26 p["SAT"] = 5; 27 p["SUN"] = 6; 28 } 29 int gcd(int a,int b) 30 { 31 int t; 32 if(a<b) swap(a,b); 33 while(b){ 34 t=a; 35 a=b; 36 b=t%b; 37 } 38 return a; 39 } 40 int lcm(int a,int b) 41 { 42 return a/gcd(a,b)*b; 43 } 44 //高斯消元法解方程组。 45 //-2表示有浮点数解，但无整数解；-1表示无解；0表示唯一解 46 //大于0表示无穷解。并返回自由变元个数 47 int Gauss() 48 { 49 int i,j,k,max_r,col,ta,tb; 50 int LCM,temp,free_x_num,free_index; 51 for(k=0,col=0;k<equ&&col<var;k++,col++){//k表示行，col表示列 52 max_r=k;//标记绝对值最大的那个数，在该列中 53 for(i=k+1;i<equ;i++) 54 if(abs(an[i][col])>abs(an[max_r][col])) 55 max_r=i; 56 if(max_r!=k) 57 for(j=k;j<var+1;j++) 58 swap(an[k][j],an[max_r][j]); 59 if(an[k][col]==0){//如果为0则k以下的行全是0了 60 k--;//行保持不变，列增加1 61 continue; 62 } 63 for(i=k+1;i<equ;i++){ 64 if(an[i][col]!=0){ 65 LCM=lcm(abs(an[i][col]),abs(an[k][col])); 66 ta=LCM/abs(an[i][col]); 67 tb=LCM/abs(an[k][col]); 68 if(an[i][col]*an[k][col]<0) tb=-tb; 69 for(j=col;j<var+1;j++) 70 an[i][j]=((an[i][j]*ta-an[k][j]*tb)%7+7)%7; 71 } 72 } 73 } 74 //无解 75 for(i=k;i<equ;i++) 76 if(an[i][col]!=0) return -1; 77 if(k<var){ 78 return var-k; 79 } 80 //唯一解 81 for(i=var-1;i>=0;i--){ 82 temp=an[i][var]; 83 for(j=i+1;j<var;j++) 84 if(an[i][j]!=0) 85 temp=((temp-an[i][j]*x[j])%7+7)%7; 86 // if(temp%an[i][j]!=0) return -2; 87 while(temp%an[i][i]!=0) temp+=7; 88 x[i]=(temp/an[i][i])%7; 89 } 90 return 0; 91 } 92 int main(){ 93 init(); 94 int i,j,k,t,res; 95 string st,ed; 96 while(cin>>var>>equ){ 97 if(var==0&&equ==0) break; 98 memset(an,0,sizeof(an)); 99 memset(x,0,sizeof(x)); 100 memset(free_x,1,sizeof(free_x)); 101 for(i=0;i<equ;i++){ 102 cin>>k>>st>>ed; 103 t=p[ed]-p[st]; 104 t=(t%7+8)%7; 105 an[i][var]=t; 106 while(k--){ 107 scanf("%d",&j); 108 an[i][j-1]++; 109 an[i][j-1]%=7; 110 } 111 } 112 res=Gauss(); 113 if(res==0){ 114 for(i=0;i<var;i++){ 115 if(x[i]<=2) x[i]+=7; 116 } 117 for(i=0;i<var-1;i++) 118 printf("%d ",x[i]); 119 printf("%d ",x[i]); 120 } 121 else if(res==-1) 122 printf("Inconsistent data. "); 123 else printf("Multiple solutions. "); 124 } 125 return 0; 126 }