交换比率 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 itembitema和itemb应是具体的商品名称，m和n都是不大于100的正整数。这个命令断言了m个itema等价于n个itemb。如果命令是一个疑问，则以问号开头，并按如下格式：? itema = itemb表示询问itema和itemb之间的交换比率，itema和itemb是在上文的断言中曾出现过的具体的商品名称（itema和itemb不一定要在同一断言中出现）。注意： 商品名字只能用不多于20个小写字母来表示。 商品的名字用单数表示（不要用复数形式）。 最多有60种不同的商品。 对于每一对不同的商品，最多只能有一个断言。 没有永假的断言，比如, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig" 是永假。 断言中的比率不一定要是最小的，但是输出的比率一定要是最小的形式。 虽然断言中不能有大于100的数字，但疑问中可以出现比100大的数字。疑问的答案化成最小后输出。 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 60using 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;}

评论