套利是利用貨幣匯率的差異將一種貨幣的一個單位轉換為同一貨幣的多個單位。例如，假設1美元兌0.5英鎊，1英鎊兌10.0法國法郎，1法國法郎兌0.21美元。然后，通過兌換貨幣，一個聰明的交易者可以從1美元開始購買0.5 * 10.0 * 0.21 = 1.05美元，賺取5%的利潤。

您的工作是編寫一個程序，該程序以貨幣匯率列表作為輸入，然后確定套利是否可能。

輸入

輸入文件將包含一個或多個測試用例。每個測試用例的第一行有一個整數n (1<=n<=30)，表示不同貨幣的數量。接下來的n行每一行都包含一種貨幣的名稱。在名稱中不會出現空格。下一行包含一個整數m，表示接下來的表的長度。最后m行分別包含源貨幣的名稱ci、表示從ci到cj的匯率的實數rij和目標貨幣的名稱cj。不出現在表中的交換是不可能的。

測試用例之間用空行隔開。對于n，輸入以0(0)結束。

輸出

對于每個測試用例，用“case case: Yes”和“case case: 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
Sample Output
Case 1: Yes
Case 2: No

分析與解答：

這題利用SPFA，但是不同于一般的SPFA。
一般我們用SPFA是給一個起點我們用dis[i]存起點到終點i的最短距離。
Map[a][b]=k，a換到b的匯率
Map[a][a]=1,意思是a換到a的匯率為1
dis[a]=j，起點換到a的匯率的最大值
先明白一個基本常識，a換到b匯率為x，b換到c匯率為y，那么a換到c匯率為x*y。然而路徑是相加的
所以這個題用SPFA時候，我們初始化變了，我們判斷條件也變了，而且根據題意除了存dis數組之外，我們還需要判斷dis[start]是不是大于1

為什么dis[start]會變？這就是SPFA算法和bfs的區(qū)別，bfs是x出隊之后就不入隊了，而SPFA中，一個點改進過其它的點之后，過了一段時間可能本身被改進(重新入隊)，于是再次用來改進其它的點

參考代碼：
https://blog.csdn.net/lyhvoyage/article/details/19248927

#include<cstdio> #include<cstring> #include<queue> #include<map> #include<string> #include<iostream> using namespace std;const int N = 35; int n, m; double d[N], Map[N][N]; int SPFA(int start) {queue<int> q;bool inq[N];for(int i = 0; i < n; i++)d[i] = 0;memset(inq, 0, sizeof(inq));d[start] = 1;q.push(start);while(!q.empty()){int x = q.front(); q.pop();inq[x] = false;for(int i = 0; i < n; i++){if(d[i] < d[x] * Map[x][i]){d[i] = d[x] * Map[x][i];if(d[start] > 1.0)return 1;if(!inq[i]){inq[i] = true;q.push(i);}}}}return 0; }int main() {int i, j, cas = 0;char s1[35], s2[35];double s;map<string,int> mp;while(~scanf("%d",&n) && n){for(i = 0; i < n; i++){for(j = 0; j < n; j++){if(i == j)Map[i][j] = 1;elseMap[i][j] = 0;}}string name;for(i = 0; i < n; i++){cin>>name;mp[name]=i;}scanf("%d",&m);for(i = 0; i < m; i++){scanf("%s%lf%s",s1, &s, s2);Map[mp[s1]][mp[s2]] = s;}int flag = 0;for(i = 0; i < n; i++){if(SPFA(i) == 1){flag = 1;break;}}printf("Case %d: ",++cas);printf("%s\n", flag ? "Yes" : "No");}return 0; }

總結

以上是生活随笔為你收集整理的（SPFA+最短路变形+回路对起点的影响）Arbitrage的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。