东莞企业网站建设制作,o2o商超网站建设,聊城高新区建设局网站,桂林两江四湖船票官网题目链接#xff1a;HDU 1217 Arbitrage 简单的货币转换问题#xff0c;给定多种货币#xff0c;以及货币之间的汇率#xff0c;问能否通过货币的转换实现收益。 例如#xff1a; 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 F… 题目链接HDU 1217 Arbitrage 简单的货币转换问题给定多种货币以及货币之间的汇率问能否通过货币的转换实现收益。 例如 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 1.05 US dollars, making a profit of 5 percent. 【解法1】 Floyd算法。 Floyd算法可以求任意两点的最短距离 这里通过小小的变形。求最大”收益“ #include iostream
#include cstdio
#include algorithm
#include map
using namespace std;
double maze[40][40];
int main(){int cas1;int n;while(scanf(%d,n)!EOF n){char tmp[30];mapstring,intmp;for(int i0;in;i){scanf( %s,tmp);mp[tmp] i;}int m;scanf(%d,m);char st[30],end[30];double rate;memset(maze,0,sizeof(maze)); //初始化为 0 maze[0][0] 1; //起点为1for(int i0;im;i){scanf( %s%lf%s,st,rate,end);maze[mp[st]][mp[end]] rate;}for(int k0;kn;k){for(int i0;in;i){for(int j0;jn;j){if(maze[i][j] maze[i][k] * maze[k][j]){ //这里是乘法看是否通过汇率转换实现增大本金maze[i][j] maze[i][k] * maze[k][j];}}}}coutCase cas: ;if(maze[0][0] 1){coutYesendl;}else coutNoendl;}return 0;
}【解法2】 SPFA 判环 如果起点可以通过汇率转换增大。那么在SPFA的松弛操作中会无限加入队列判断是否重复加入n次以上即可。 和我上一篇博客的解法一致。 #include iostream
#include cstdio
#include algorithm
#include cstring
#include queue
#include map
using namespace std;
double maze[40][40];
const int maxn 40;
double dis[maxn]; //记录各个种类money的当前值初始化为0 起点为1
bool vis[maxn]; //标记是否在队列之中
int cnt[maxn]; //判环
int n;
int SPFA(){queueintQ;Q.push(0); vis[0]1; dis[0] 1;cnt[0];while(!Q.empty()){int now Q.front(); Q.pop(); vis[now] false;for(int i0;in;i){double rate maze[now][i];if(dis[i] dis[now] * rate) //如果可以增大{dis[i] dis[now] * rate;if(!vis[i]){vis[i]1;Q.push(i);}if(cnt[i] n){ //如果节点加入队列超过n次return -1;}}}return 1;
}
void init(){memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(cnt));memset(dis,0,sizeof(dis));
}
int main(){int cas1;mapstring,intmp;while(scanf(%d,n)!EOF n){char tmp[30];mp.clear();for(int i0;in;i){scanf( %s,tmp);mp[tmp] i;}int m;scanf(%d,m);char st[30],end[30];double rate;init();maze[0][0] 1;for(int i0;im;i){scanf( %s%lf%s,st,rate,end);maze[mp[st]][mp[end]] rate;}int ret SPFA();coutCase cas: ;if(ret -1)coutYesendl;else coutNoendl;}return 0;
} 转载于:https://www.cnblogs.com/chaiwenjun000/p/5321162.html
