[USACO3.2.4 Feed Ratios]

本文主要是介绍[USACO3.2.4 Feed Ratios]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

给出三组整数，表示 大麦：燕麦：小麦 的比例，找出用这三种饲料调配 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。一种混合物的比例不会由其他混合物的比例直接相加得到。 

Input

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

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

Output

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

Sample Input

3 4 5
1 2 3
3 7 1
2 1 2 

Sample Output

8 1 5 7

Source

高斯消元法 // czyuan大神的模板

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn = 5;
int equ,var;/// equ个方程，var个变量
int a[maxn][maxn];
int x[maxn];///解
bool free_x[maxn];///不确定变元
int free_num;
void debug()
{for(int i=0;i<equ;i++){for(int j=0;j<var+1;j++)printf("%d ",a[i][j]);printf("\n");}printf("\n");
}
int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}
int lcm(int a,int b)
{return a/gcd(a,b)*b;
}
/// -2表示浮点解 -1表示无解 0表示唯一解 大于0表示自由变元个数
int gauss()
{int i,j,k;int max_r;int col=0;int ta,tb;int LCM;int tmp;int free_x_num;int free_index;for(k=0;k<equ&&col<var;k++,col++){max_r=k;for(i=k+1;i<equ;i++){if(abs(a[i][col])>abs(a[max_r][col]))max_r=i;}if(max_r!=k){for(j=k;j<var+1;j++)swap(a[k][j],a[max_r][j]);}if(a[k][col]==0){k--;continue;}for(i=k+1;i<equ;i++){if(a[i][col]!=0){LCM=lcm(abs(a[i][col]),abs(a[k][col]));ta=LCM/abs(a[i][col]);tb=LCM/abs(a[k][col]);if(a[i][col]*a[k][col]<0)tb=-tb;for(j=col;j<var+1;j++)a[i][j]=a[i][j]*ta-a[k][j]*tb;}}}for(i=k;i<equ;i++)if(a[i][col]!=0)return -1; /// 无解if(k<var) /// 无穷解{for(i=k-1;i>=0;i--){free_x_num=0;for(j=0;j<var;j++){if(a[i][j]!=0&&free_x[j]){free_x_num++;free_index=j;}}if(free_x_num>1)continue;tmp=a[i][var];for(j=0;j<var;j++){if(a[i][j]!=0&&j!=free_index)tmp-=a[i][j]*x[j];}x[free_index]=tmp/a[i][free_index];free_x[free_index]=0;}return var-k;}for(i=var-1;i>=0;i--){tmp=a[i][var];for(j=i+1;j<var;j++)if(a[i][j]!=0)tmp-=a[i][j]*x[j];if(tmp%a[i][i]!=0)return -2;x[i]=tmp/a[i][i];}return 0;
}
int main()
{equ=3;var=3;int cnt[4][4];int xx,yy,zz;int ans;scanf("%d%d%d",&xx,&yy,&zz);for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&cnt[i][j]);for(ans=1;ans<101;ans++){for(int i=0;i<3;i++)for(int j=0;j<3;j++)a[j][i]=cnt[i][j];a[0][3]=ans*xx;a[1][3]=ans*yy;a[2][3]=ans*zz;free_num=gauss();if(free_num>=0){if(free_num==0){if(x[0]<0||x[1]<0||x[2]<0)continue;printf("%d %d %d %d\n",x[0],x[1],x[2],ans);}else{if((!free_x[0]&&x[0]<0)||(!free_x[1]&&x[1]<0)||(!free_x[2]&&x[2]<0))continue;for(int i=0;i<3;i++){if(free_x[i])printf("0 ");elseprintf("%d ",x[i]);}printf("%d\n",ans);}break;}}if(ans==101)printf("NONE\n");return 0;
}

这篇关于[USACO3.2.4 Feed Ratios]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---