合肥今天的最新消息/深圳seo优化服务
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，且1 法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。 给定n 种货币c1 ,c2 ,... ,cn的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。
输入
含多个测试数据项。每个测试数据项的第一行中只有1 个整数n (1< =n< =30)，表示货币总数。其后n行给出n种货币的名称。接下来的一行中 有1 个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有3 个数据项ci， rij和cj，表示货币ci和cj的兑换率为 rij。文件最后以数字0 结束。
输出
对每个测试数据项j，如果存在套汇的可能性则输出“Case j Yes”， 否则输出“Case j No”。
样例输入
3
USDollar BritishPound FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3
USDollar BritishPound FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar 0
样例输出
Case 1 Yes
Case 2 No
#include <iostream>
#include <cstring>
using namespace std;
int statck[1000000];
int status[100];
double res[100];
class num
{ public: int end; double val; int next;
}a[1000000];
int b[100];
int sum[100],tag,w;
string s1[100];
int n;
int main()
{ void deal(int k); int i,j,m,s,t,x,y,z; string s2,s3; double val; t=1; while(cin>>n) { if(!n) { break; } for(i=1;i<=n;i++) { cin>>s1[i]; } cin>>m; memset(b,-1,sizeof(b)); z=0; for(i=1;i<=m;i++) { cin>>s2; cin>>val; cin>>s3; for(j=1;j<=n;j++) { if(s1[j]==s2) { x=j; } if(s1[j]==s3) { y=j; } } a[z].end=y; a[z].val=val; a[z].next=b[x]; b[x]=z; z++; } for(i=1;i<=n;i++) { tag=0; deal(1); if(tag==1) { break; } } cout<<"Case "<<t<<" "; t++; if(i==n+1) { cout<<"No"<<endl; }else { cout<<"Yes"<<endl; } } return 0; } void deal(int k) { int i,j,base,top; int x; for(i=1;i<=n;i++) { res[i]=0; } res[k]=100.0; base=top=0; memset(status,0,sizeof(status)); memset(sum,0,sizeof(sum)); statck[top++]=k; status[k]=1; sum[k]+=1; w=0; while(base<top) { x=statck[base]; base++; status[x]=0; for(j=b[x];j!=-1;j=a[j].next) { if((res[x]*a[j].val)>res[a[j].end]) { res[a[j].end]=res[x]*a[j].val; if(status[a[j].end]==0) { sum[a[j].end]+=1; statck[top++]=a[j].end; status[a[j].end]=1; if(sum[a[j].end]>=n) { tag=1; break; } } } } if(j!=-1) { break; } } }