（SPFA+最短路变形+回路对起点的影响）Arbitrage

套利是利用货币汇率的差异将一种货币的一个单位转换为同一货币的多个单位。例如，假设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的区别，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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。