| 交换比率 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 9, Accepted users: 9 |
| Problem description |
|
用纸币来支付商品和服务的费用可以使生活方便，可是人们有时希望能够直接交换物品而不使用钱币来作媒介。为了确保一致的“价格”，商人们制订了一个关于商品的交换比率。我们用正整数M和N来表示商品A和B的交换比率，并说M个商品A等价于N个商品B。举例来说，2个火炉应该等价于3个冰箱(从数学的角度来说，1个火炉等价于1.5个冰箱,但是要拿出半个冰箱不是件容易的事,交换比率总是那些有实际意义的整数)。 请写一个程序，对于给出的交换比率表，计算出任意两件商品的交换比率。 |
| Input |
| 输入有一个或多个命令,结尾用一个“.”号来表示。 每个命令独占一行，命令可以是一个断言或一个疑问。如果是断言，则以感叹号开头，并按如下格式： ! m itema = n itemb itema和itemb应是具体的商品名称，m和n都是不大于100的正整数。这个命令断言了m个itema等价于n个itemb。如果命令是一个疑问，则以问号开头，并按如下格式： ? itema = itemb 表示询问itema和itemb之间的交换比率，itema和itemb是在上文的断言中曾出现过的具体的商品名称（itema和itemb不一定要在同一断言中出现）。 注意：
|
| Output |
| 对于每个疑问，根据所有的有关的断言，输出itema和itemb之间的交换比率。交换比率必须是整数形式而且应该尽可能的小。如果不能找到相应的交换比率，用问号代替整数来表示。 |
| Sample Input |
! 6 shirt = 15 sock ! 47 underwear = 9 pant ? sock = shirt ? shirt = pant ! 2 sock = 1 underwear ? pant = shirt . |
| Sample Output |
5 sock = 2 shirt ? shirt = ? pant 45 pant = 188 shirt |
| Problem Source |
| HNU Contest |
///// 题目不是很难，主要商品之间的关系难理清
思路：将各商品的名字映射为数组下标，商品之间的关系用一个二维矩阵 nMerchInfo[][]保存
设 n Merch1 = m Merch2 , Merch1 映射为下标 i,Merch2 映射为下标 j，则nMerchInfo[i][j]
记录 n, nMerchInfo[j][i] 记录 m; 于是寻找 i, j 商品间的等价关系，可以通过递归查找矩阵
如果 nMerchInfo[i][j] 有值则直接输出，否则如果有解必定是通过某个中间商品 k 求取,于是
通过 nMerchInfo[i][k], nMerchInfo[k][j] 就可得结果。
#pragma warning(disable:4786)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define MAX_MERCH 60
using namespace std;
typedef pair<string,int> t_MerchNode;
typedef vector<t_MerchNode> t_MerchIndex;
typedef pair<int,int> t_Result;
int nMerchInfo[MAX_MERCH][MAX_MERCH]={0};
bool bFind[MAX_MERCH][MAX_MERCH];
t_Result getResult(int i, int j, int gIndex){ // 递归寻找中间商品
t_Result tp;
for(int it=0; it<gIndex; it++)
if(!bFind[i][it] && nMerchInfo[i][it]!=0){
if(it==j)
return t_Result(nMerchInfo[i][j],nMerchInfo[j][i]);
else{
bFind[i][it] = true;
tp = getResult(it,j,gIndex);
if(tp.first != -1)
return t_Result( nMerchInfo[i][it] * tp.first,
tp.second * nMerchInfo[it][i] );
}
}
return t_Result(-1,-1);
}
void minDealResult(t_Result& p){ // 最小化结果
int a=p.first, b=p.second, t;
for(t=b; a%b; t=b){
b = a%b;
a = t;
}
p.first /= b;
p.second /= b;
}
int myFind(t_MerchIndex& index, string str){ // 商品名映射为数组下标
for(int i=0; i<index.size(); i++)
if(str==index[i].first)
return index[i].second;
return -1;
}
int main(){
t_MerchIndex mIndex;
char c;
for(int gIndex=0; cin>>c && c!='.'; ){
int a,b,i,j;
string strMerch1,strMerch2;
if(c=='!'){
cin>>a>>strMerch1>>c>>b>>strMerch2;
if((i=myFind(mIndex,strMerch1))==-1){
i = gIndex;
mIndex.push_back(t_MerchNode(strMerch1,gIndex++));
}
if((j=myFind(mIndex,strMerch2))==-1){
j = gIndex;
mIndex.push_back(t_MerchNode(strMerch2,gIndex++));
}
nMerchInfo[i][j] = a;
nMerchInfo[j][i] = b;
}else{
cin>>strMerch1>>c>>strMerch2;
if( (i=myFind(mIndex,strMerch1)) == -1 ||
(j=myFind(mIndex,strMerch2)) == -1 ){
cout<<"? "<<strMerch1<<" = ? "<<strMerch2<<endl;
continue;
}
t_Result p;
if(nMerchInfo[i][j]!=0){
p.first = nMerchInfo[i][j];
p.second = nMerchInfo[j][i];
minDealResult(p);
cout<<p.first<<" "<<strMerch1<<" = "<<p.second<<" "<<strMerch2<<endl;
continue;
}
memset(bFind,false,sizeof(bool)*MAX_MERCH*MAX_MERCH);
p = getResult(i,j,gIndex);
if(p.first==-1)
cout<<"? "<<strMerch1<<" = ? "<<strMerch2<<endl;
else{
minDealResult(p);
cout<<p.first<<" "<<strMerch1<<" = "<<p.second<<" "<<strMerch2<<endl;
}
}
}
return 0;
}
评论