HDU 1217 Arbitrage (Floyd + SPFA判環)

題目鏈接：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 cas=1;int n;while(scanf("%d",&n)!=EOF && n){char tmp[30];map<string,int>mp;for(int i=0;i<n;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; //起點為1；for(int i=0;i<m;i++){scanf(" %s%lf%s",st,&rate,end);maze[mp[st]][mp[end]] = rate;}for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(maze[i][j] < maze[i][k] * maze[k][j]){ //這里是乘法，看是否通過匯率轉換實現增大本金；maze[i][j] = maze[i][k] * maze[k][j];}}}}cout<<"Case "<<cas++<<": ";if(maze[0][0] > 1){cout<<"Yes"<<endl;}else cout<<"No"<<endl;}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(){queue<int>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;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 cas=1;map<string,int>mp;while(scanf("%d",&n)!=EOF && n){char tmp[30];mp.clear();for(int i=0;i<n;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 i=0;i<m;i++){scanf(" %s%lf%s",st,&rate,end);maze[mp[st]][mp[end]] = rate;}int ret = SPFA();cout<<"Case "<<cas++<<": ";if(ret == -1)cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}