HDU 1217 Arbitrage (Floyd + SPFA判环)-白红宇

HDU 1217 Arbitrage (Floyd + SPFA判环)

阅读量：4640 次

发布时间：2019-06-09

本文共 1524 字，大约阅读时间需要 5 分钟。

题目链接：

简单的货币转换问题，给定多种货币，以及货币之间的汇率，问能否通过货币的转换实现收益。

例如：

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 
    
     #include 
     
      #include 
      
       #include 
       using namespace std;double maze[40][40];int main(){    int cas=1;    int n;    while(scanf("%d",&n)!=EOF && n){        char tmp[30];        map
        
         mp;        for(int i=0;i
         
           1){ cout<<"Yes"<

【解法2】

SPFA 判环，如果起点可以通过汇率转换增大。那么在SPFA的松弛操作中会无限加入队列，判断是否重复加入n次以上即可。

和我的解法一致。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         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(){ queue
          
           Q; 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 i=0;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 cas=1; map
            
             mp; while(scanf("%d",&n)!=EOF && n){ char tmp[30]; mp.clear(); for(int i=0;i

转载于:https://www.cnblogs.com/chaiwenjun000/p/5321162.html

你可能感兴趣的文章