【描述】
农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。
给出三组整数，表示 大麦：燕麦：小麦 的比例，找出用这三种饲料调配 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”。前三个整数表示三种饲料的份数，用这样的配比可以得到目标饲料。第四个整数表示混合三种饲料后得到的目标饲料的份数。
【分析】
可以用枚举，不会超时，但是会很慢。
这里给出用高斯消元的做法，枚举目标量。然后判断是否有解就行了。
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
using namespace std;
int data[][];
int A[][];//求解
void init(int num);
int gauss(int n);//高斯消元
void debug();
int gcd(int a,int b){return b==?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int main()
{
int i;
//文件操作
freopen("ratios.in","r",stdin);
freopen("ratios.out","w",stdout);
memset(data,,sizeof(data));
//输入数据
scanf("%d%d%d",&data[][],&data[][],&data[][]);
for (i=;i<;i++) scanf("%d%d%d",&data[i][],&data[i][],&data[i][]);
for (i=;i<=;i++)
{
init(i);//初始化
if (gauss(i)) return ;
}
printf("NONE");
return ;
}
void init(int num)
{
int i,j;
for (i=;i<;i++)//行列
for (j=;j<;j++) A[i][j]=data[j][i];
A[][]=data[][]*num;
A[][]=data[][]*num;
A[][]=data[][]*num; }
void debug()//调试
{
int i,j;
for (i=;i<;i++)
{
for (j=;j<;j++) printf("%d ",A[i][j]);
printf("\n");
}
printf("\n");
}
int gauss(int m)
{
int i=,j=,k,l,r,tmp,tmp1,tmp2,ans[];
memset(ans,,sizeof(ans));
while((i<)&&(j<))//i是行数，j当前需要消除的行数
{
r=i;//绝对值最大
for(k=i+;k<;k++) if(A[k][j]>A[i][j]) r=k;
if (r!=i) for(k=;k<;k++) swap(A[i][k],A[r][k]); if(A[i][j]!=)
{
for(l=i+;l<;l++)
if(A[l][j]!=)
{
tmp=lcm(abs(A[l][j]),abs(A[i][j]));
tmp1=tmp/A[i][j];
tmp2=tmp/A[l][j];
for(k=j;k<;k++) A[l][k]=A[l][k]*tmp2-A[i][k]*tmp1;
}
i++;//行数
}
j++;
}
//debug();
if(i==)
{
for(i=;i>=;i--)
{
tmp=;
for(j=i+;j<;j++) tmp+=A[i][j]*ans[j]; if((A[i][]-tmp)%A[i][i]!=) return false;
ans[i]=(A[i][]-tmp)/A[i][i];
} if((ans[]<) || (ans[]<) || (ans[]<)) return ;//只要
printf("%d %d %d %d\n",ans[],ans[],ans[],m);
return ;
}
else return ;
}