【组队赛#5】BNU 4291 Arbitrage? （floyd最短路 map映射）

【组队赛#5】BNU 4291 Arbitrage? （floyd最短路 map映射）

【题目链接】​​click here~~​​

【题目大意】去多个国家旅游，给定国与国之间汇率的转化率，如果从起点出发最后回到起点，有收益则符合，否则不符合

【解题思路】

判一次环，用floyd计算距离最短的而且转换率最大的，map映射  <字符串--点>

代码

/*BNUOJ 4291 Arbitrage?Author :HRW判一次环，用floyd计算距离最短的而且转换率最大的map映射 <字符串--点>*/#include using namespace std;const int maxn = 300;double dp[maxn][maxn];mapmapp;double eps = 1e-8;int main(){ int n,m,i,j,k,a,b,t; string s,s1,s2; while(cin>>n,n) { memset(dp,0,sizeof(dp)); for(i=1; i<=n; i++) { cin>>s; mapp[s]=i;//将字符串映射到i dp[i][i]=1;//初始化本身距离为1 } cin>>m; double x,y; for(i=0; i>s1>>s2; scanf("%lf:%lf",&x,&y); dp[mapp[s1]][mapp[s2]]=y/x;//s1 到s2转换率 } for(k=1; k<=n; k++){//floyd计算距离最短的转换率最大 for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ dp[i][j]=max(dp[i][j],dp[i][k]*dp[k][j]); } } } bool flag=false; for(i=1; i<=n; i++){ if(dp[i][i]>1.0){//存在 flag=true; break; } } if(flag) puts("Arbitrage"); else puts("Ok"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。