【USACO 3.2.4】饲料调配

【描述】

农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。

给出三组整数，表示大麦：燕麦：小麦的比例，找出用这三种饲料调配 x：y：z 的饲料的方法。

例如，给出目标饲料 3：4：5 和三种饲料的比例：

    1:2:3   
    3:7:1  
    2:1:2

你必须编程找出使这三种饲料用量最少的方案，要是不能用这三种饲料调配目标饲料，输出“NONE”。“用量最少”意味着三种饲料的用量（整数）的和必须最小。

对于上面的例子，你可以用8份饲料1，1份饲料2，和5份饲料3，来得到7份目标饲料：

8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)

表示饲料比例的整数以及目标饲料的都是小于100的非负整数。表示各种饲料的份数的整数，都小于100。一种混合物的比例不会由其他混合物的比例直接相加得到。

【格式】

PROGRAM NAME: ratios

INPUT FORMAT:

(file ratios.in)

Line 1: 三个用空格分开的整数，表示目标饲料

Line 2..4: 每行包括三个用空格分开的整数，表示农夫约翰买进的饲料的比例

OUTPUT FORMAT:

(file ratios.out)

输出文件要包括一行，这一行要么有四个整数，要么是“NONE”。前三个整数表示三种饲料的份数，用这样的配比可以得到目标饲料。第四个整数表示混合三种饲料后得到的目标饲料的份数。

【分析】

可以用枚举，不会超时，但是会很慢。

这里给出用高斯消元的做法，枚举目标量。然后判断是否有解就行了。

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <iostream>
 7 #include <fstream>
 8 using namespace std;
 9 int data[100][100];
10 int A[100][100];//求解 
11 void init(int num);
12 int gauss(int n);//高斯消元 
13 void debug();
14 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
15 int lcm(int a,int b){return a*b/gcd(a,b);}
16 int main()
17 {
18     int i;
19     //文件操作
20     freopen("ratios.in","r",stdin);
21     freopen("ratios.out","w",stdout); 
22     memset(data,0,sizeof(data));
23     //输入数据 
24     scanf("%d%d%d",&data[3][0],&data[3][1],&data[3][2]);
25     for (i=0;i<3;i++) scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
26     for (i=1;i<=100;i++)
27     {
28         init(i);//初始化 
29         if (gauss(i)) return 0;
30     }
31     printf("NONE");
32     return 0;
33 }
34 void init(int num)
35 {
36      int i,j;
37      for (i=0;i<3;i++)//行列 
38      for (j=0;j<3;j++) A[i][j]=data[j][i];
39      A[0][3]=data[3][0]*num;
40      A[1][3]=data[3][1]*num;
41      A[2][3]=data[3][2]*num;
42      
43 }
44 void debug()//调试 
45 {
46      int i,j;
47      for (i=0;i<3;i++)
48      {
49          for (j=0;j<4;j++) printf("%d ",A[i][j]);
50          printf("
");
51      }
52      printf("
");
53 }
54 int gauss(int m) 
55 {
56     int i=0,j=0,k,l,r,tmp,tmp1,tmp2,ans[5];
57     memset(ans,0,sizeof(ans));
58     while((i<3)&&(j<4))//i是行数，j当前需要消除的行数 
59     {
60         r=i;//绝对值最大 
61         for(k=i+1;k<3;k++) if(A[k][j]>A[i][j]) r=k;
62         if (r!=i) for(k=0;k<4;k++) swap(A[i][k],A[r][k]);
63         
64         if(A[i][j]!=0)
65         {
66             for(l=i+1;l<3;l++)
67             if(A[l][j]!=0)
68             {
69                 tmp=lcm(abs(A[l][j]),abs(A[i][j]));
70                 tmp1=tmp/A[i][j];
71                 tmp2=tmp/A[l][j];
72                 for(k=j;k<4;k++) A[l][k]=A[l][k]*tmp2-A[i][k]*tmp1;
73             }
74             i++;//行数 
75         }
76         j++; 
77     }
78     //debug();
79     if(i==3)
80     {
81             for(i=2;i>=0;i--)
82             {
83                 tmp=0;
84                 for(j=i+1;j<3;j++) tmp+=A[i][j]*ans[j];
85                 
86                 if((A[i][3]-tmp)%A[i][i]!=0) return false;
87                 ans[i]=(A[i][3]-tmp)/A[i][i];
88             }
89             
90       if((ans[0]<0) || (ans[1]<0) || (ans[2]<0)) return 0;//只要 
91       printf("%d %d %d %d
",ans[0],ans[1],ans[2],m);
92       return 1;
93    }
94    else return 0;
95 }