1. 从一道汇率题说起：Arbitrage到底在问什么
Arbitrage这个词在金融领域叫"套利"，放到算法竞赛里，它被抽象成了一个非常干净的图论问题。题目大意是这样的：给你若干种货币，再给你若干组货币之间的兑换汇率，问你能不能通过一系列兑换操作，让手里的钱变多。听起来像是金融题，实际上它是一道彻头彻尾的图论题，核心考点就两个——SPFA判断负环和map做货币名到编号的映射。
我第一次遇到这道题的时候，第一反应是"这不就是个乘法吗，挨个试不就行了"。但仔细一想，货币种类可能有几十种，兑换路径的组合是指数级增长的，暴力枚举根本不可行。这时候就需要把它转化成图论模型：把每种货币看成一个节点，把兑换关系看成一条有向边，边的权值就是汇率。那么问题就变成了——在这个有向图中，是否存在一个环，使得环上所有边的权值乘积大于1。
为什么是乘积大于1？因为你从某种货币出发，经过一圈兑换回到同一种货币，如果最终金额比出发时多，那就说明存在套利机会。比如你有1个单位A货币，经过A→B→C→A的兑换后变成了1.05个单位A，那你就白赚了0.05，这就是套利。
但SPFA算法本身是用来判断负环的，它处理的是加法意义上的环权值和小于0的情况。这里我们要处理的是乘法意义上的环权值积大于1。这两者之间怎么转换？这就是这道题最核心的一个思维跳跃，也是很多人卡住的地方。我在下面会详细拆解这个转换过程，保证你看完之后能自己推导出来，而不是死记结论。
这道题适合谁看？如果你正在学图论、刚接触SPFA、或者对"负环"这个概念只停留在模板层面而不知道怎么灵活运用，那这篇内容就是写给你的。我会从建模思路、算法选择、代码实现、常见坑点四个维度把它讲透，让你下次遇到类似的"乘积型环检测"问题能直接上手。
2. 把汇率兑换翻译成图论语言：建模的完整推导
2.1 为什么是"环"而不是"路径"
很多人一开始会想：我只要找到一条兑换路径，让最终金额变大不就行了吗？为什么非要找环？
这里的关键在于，题目问的是"能不能通过套利让钱变多"，而套利的标准定义是无风险获利。如果你只是找到一条从A到B的路径使得B的金额大于A，这并不构成套利，因为你手里的货币种类变了，你并没有"回到原点"。真正的套利必须是从某种货币出发，经过一系列兑换后回到同一种货币，且金额增加。这在图论里对应的就是一个环。
所以问题的本质是：在一个有向加权图中，是否存在一个环，使得环上所有边的权值之积大于1。
2.2 乘积大于1怎么变成加法负环
SPFA判断负环的标准形式是：如果存在一个环，环上所有边的权值之和小于0，那么这个环就是负环，SPFA可以通过检测某个节点入队次数超过n-1次来判断负环存在。
现在我们的条件是环上权值之积大于1。怎么把乘法变成加法？答案是取对数。
对不等式两边同时取自然对数：
- 原条件：w1 × w2 × ... × wk > 1
- 取对数后：ln(w1) + ln(w2) + ... + ln(wk) > ln(1) = 0
- 即：ln(w1) + ln(w2) + ... + ln(wk) > 0
我们要把它变成"小于0"的形式来套SPFA负环模板，只需要再取负号：
- -(ln(w1) + ln(w2) + ... + ln(wk)) < 0
- 也就是：(-ln(w1)) + (-ln(w2)) + ... + (-ln(wk)) < 0
所以，我们只需要把每条边的权值设为-ln(汇率)，然后跑SPFA判断是否存在负环即可。如果存在负环，说明原图中存在乘积大于1的环，即存在套利机会。
这个转换是整个算法的灵魂。我在第一次推导的时候卡在了"为什么要取负号"上，后来想明白了：SPFA的模板是判断"和小于0"，而我们的原始条件是"积大于1"，取对数后变成"和大于0"，再取负号就变成"和小于0"，完美对应。
2.3 为什么不用Bellman-Ford或者Floyd
理论上，判断负环可以用Bellman-Ford，也可以用Floyd。但这道题里SPFA是更优的选择，原因如下：
| 算法 | 时间复杂度 | 适用场景 | 本题是否推荐 |
|---|---|---|---|
| Bellman-Ford | O(VE) | 边数较少时可用 | 可以但不必要 |
| Floyd | O(V³) | 需要全源最短路时 | 不推荐，杀鸡用牛刀 |
| SPFA | 平均O(kE)，最坏O(VE) | 稀疏图、负环检测 | 推荐 |
这道题的图通常是稀疏图（货币种类不多，兑换关系也不会太密集），SPFA的平均性能很好。而且SPFA的负环检测逻辑非常直观：如果一个节点入队次数超过n-1次，说明存在负环。这个判据的数学依据是：在没有负环的情况下，任何节点的最短路径最多经过n-1条边，对应最多被松弛n-1次。如果超过了，必然是因为负环导致路径可以无限缩短。
2.4 map在这里扮演什么角色
题目给的是货币名称，比如"USD"、"EUR"、"GBP"这样的字符串，但图论算法处理的是整数编号。所以我们需要一个从字符串到整数的映射。map<string, int>就是干这个的。
为什么不用哈希表？因为map在C++里是有序的，而且对于这道题的数据规模来说，map的性能完全够用。更重要的是，map的用法简单直观，不需要手写哈希函数，不容易出错。当然，如果你追求极致性能，用unordered_map也可以，但要注意unordered_map在某些评测环境下可能因为哈希冲突被卡常数。
我在实际写的时候，习惯用map<string, int>来建立映射，同时用一个vector 来保存反向映射（虽然这道题不需要反向映射，但养成习惯没坏处）。每次读入一个货币名称，先查map里有没有，没有就分配一个新编号。
3. SPFA判断负环的完整实现与关键细节
3.1 SPFA的核心逻辑回顾
SPFA本质上是Bellman-Ford的队列优化版本。它的基本流程是：
- 把源点入队，标记源点在队列中
- 当队列不为空时，取出队首节点u
- 遍历u的所有邻接边，如果通过u可以松弛某个邻接点v（即dist[u] + w < dist[v]），就更新dist[v]
- 如果v不在队列中，把v入队
- 重复直到队列为空
判断负环的关键在于：记录每个节点的入队次数。如果某个节点的入队次数达到了n次（或者松弛次数达到n次），就说明存在负环。
为什么是n次而不是n-1次？因为源点本身会入队一次，所以总共最多入队n次。如果第n+1次入队，就说明有负环。不过不同人的写法略有差异，有的人判断入队次数>=n，有的人判断松弛次数>=n，本质上是一样的。
3.2 本题的SPFA实现细节
这道题和标准SPFA有一个很大的不同：源点不唯一，而且我们需要检测整个图里是否存在负环，而不是从某个源点出发能否到达负环。
标准SPFA通常是从一个源点出发，判断从该源点能否到达负环。但这道题里，套利机会可能存在于任何货币组合中，所以我们需要检测整个图。解决方案是：把所有节点都作为源点初始入队。
具体做法是：
- 初始化所有节点的dist为0（或者任意值，因为我们要找的是环，不是最短路径）
- 把所有节点都加入队列
- 所有节点的入队次数初始化为1（或者0，取决于你的判据）
- 然后跑SPFA
这样做的逻辑是：我们相当于在一个超级源点连向所有节点的图上跑SPFA，超级源点到每个节点的距离为0。这样任何负环都会被检测到。
还有一个细节：dist数组的初始值。因为我们要判断的是"是否存在负环"，而不是"从源点到某点的最短距离"，所以dist的初始值可以全部设为0。在松弛的时候，如果dist[u] + w < dist[v]，就更新。由于初始都是0，第一次松弛时只要w < 0就会更新，这正好对应了负权边。
3.3 边的权值计算与精度问题
前面推导过，边的权值应该是-ln(汇率)。在代码里就是：
double w = -log(rate);这里用log而不是log10，其实用哪个都可以，因为换底公式只差一个常数因子，不影响正负性。但习惯上用自然对数。
精度问题是这道题的一个隐藏坑点。因为涉及浮点数比较，直接用<比较可能会有误差。不过SPFA的松弛条件是dist[u] + w < dist[v]，这个比较本身对精度不敏感，因为只要存在负环，dist值会不断减小，最终一定会触发入队次数超限。真正需要注意的是输出格式和多组数据的处理。
3.4 完整代码框架
#include <iostream> #include <cstring> #include <cmath> #include <queue> #include <map> #include <string> #include <vector> using namespace std; const int MAXN = 35; const double EPS = 1e-8; struct Edge { int to; double w; }; vector<Edge> edges[MAXN]; double dist[MAXN]; int cnt[MAXN]; // 入队次数 bool inQueue[MAXN]; int n, m; bool spfa() { queue<int> q; memset(dist, 0, sizeof(dist)); memset(cnt, 0, sizeof(cnt)); memset(inQueue, false, sizeof(inQueue)); // 所有节点入队 for (int i = 1; i <= n; i++) { q.push(i); inQueue[i] = true; cnt[i] = 1; } while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (int i = 0; i < edges[u].size(); i++) { int v = edges[u][i].to; double w = edges[u][i].w; if (dist[u] + w < dist[v] - EPS) { dist[v] = dist[u] + w; cnt[v]++; if (cnt[v] > n) { return true; // 存在负环 } if (!inQueue[v]) { q.push(v); inQueue[v] = true; } } } } return false; } int main() { int caseNum = 0; while (cin >> n && n) { caseNum++; map<string, int> id; string name; for (int i = 1; i <= n; i++) { cin >> name; id[name] = i; edges[i].clear(); } cin >> m; for (int i = 0; i < m; i++) { string from, to; double rate; cin >> from >> rate >> to; int u = id[from]; int v = id[to]; edges[u].push_back({v, -log(rate)}); } if (spfa()) { cout << "Case " << caseNum << ": Yes" << endl; } else { cout << "Case " << caseNum << ": No" << endl; } } return 0; }这段代码有几个地方值得注意：
第一，cnt[i] = 1的初始化。因为所有节点一开始就入队了，所以初始入队次数是1。判断条件是cnt[v] > n，也就是入队次数超过n次就判定负环。
第二，dist[u] + w < dist[v] - EPS中的EPS。加一个微小的偏移量是为了避免浮点误差导致的误判。不过这道题里其实不加EPS也能过，因为负环的检测依赖于入队次数，而不是最终的dist值。
第三，多组数据的处理。每次循环都要清空edges数组和map，否则会影响到下一组数据。
4. 那些年我在这道题上踩过的坑
4.1 坑一：把"乘积大于1"直接当成"和大于0"来处理
这是我第一次做这道题时犯的错误。我当时想，既然乘积大于1就是套利，那我直接把汇率当成边权，判断有没有环的权值和大于0不就行了？然后我写了一个SPFA，把松弛条件改成dist[u] + w > dist[v]，结果样例都过不了。
问题出在：SPFA的框架是为"最短路径"设计的，它的松弛条件是"如果通过u能让v的路径更短，就更新"。如果你把条件反过来，整个算法的逻辑就崩了。正确的做法是取对数再取负号，把它转化成标准的负环检测问题。
这个坑的本质是：不要试图修改算法的核心逻辑，而是修改问题的表示方式。把乘法变加法、把大于变小于，这些都是数学变换，不涉及算法本身的改动。
4.2 坑二：只从第一个节点出发跑SPFA
标准SPFA模板通常是从一个源点出发。我一开始也是这么写的，从节点1开始跑，结果发现有些套利环根本不经过节点1，导致漏判。
正确的做法是把所有节点都作为源点初始入队。这样相当于在一个超级源点的图上跑SPFA，任何负环都逃不掉。
这个坑的教训是：当问题要求"判断整个图是否存在负环"而不是"从某点出发能否到达负环"时，必须把所有节点初始入队。
4.3 坑三：入队次数的判断条件写错
有的人写cnt[v] >= n，有的人写cnt[v] > n。这两个到底哪个对？
其实取决于你的初始化。如果你把所有节点的cnt初始化为0，然后入队时cnt++，那么判断条件应该是cnt[v] >= n。如果你初始化为1，判断条件应该是cnt[v] > n。
我个人的习惯是初始化为1，判断条件用> n。这样逻辑更清晰：一个节点最多入队n次（对应n-1条边的最短路径），第n+1次入队就说明有负环。
4.4 坑四：map的清空问题
在多组数据的题目里，map必须在每组数据开始时清空。我有一次忘了清空，导致上一组的货币名称映射残留下来，新的一组数据里出现了错误的编号对应，结果WA了好几次。
正确的做法是在每组数据开始时重新声明一个map，或者调用map.clear()。我倾向于在循环内部重新声明，这样更安全。
4.5 坑五：浮点数比较的精度问题
虽然这道题对精度不敏感，但在某些变体题目里，浮点误差可能导致误判。比如两个非常接近的汇率，取对数后差值极小，可能因为浮点误差导致松弛条件判断错误。
解决方案是加一个EPS：
if (dist[u] + w < dist[v] - 1e-8)这样只有当新路径明显更短时才更新，避免因为浮点误差反复松弛。
5. 从这道题延伸出去：乘积型环检测的通用套路
5.1 什么时候会遇到"乘积型"问题
除了汇率套利，还有很多问题可以抽象成"乘积型环检测"。比如：
- 化学反应中的物质转化率，问能否通过循环反应获得净增益
- 网络传输中的衰减/放大，问是否存在信号放大的环路
- 经济模型中的投资回报率，问是否存在无风险套利
这些问题的共同特点是：每一步操作是乘法关系，目标是判断是否存在一个环使得总效果大于1（或小于1）。
5.2 通用转换模板
对于"是否存在环使得权值乘积大于1"的问题，通用解法是：
- 把每条边的权值取对数：w' = ln(w)
- 取负号：w'' = -ln(w)
- 跑SPFA判断负环
对于"是否存在环使得权值乘积小于1"的问题，转换方式是：
- 取对数：w' = ln(w)
- 直接跑SPFA判断负环（因为ln(w) < 0对应w < 1）
对于"是否存在环使得权值乘积等于1"的问题，这个比较麻烦，因为等于1对应ln(w) = 0，不是负环。这种问题通常需要其他方法，比如判断是否有零权环。
5.3 和差分约束系统的联系
如果你学过差分约束系统，会发现这里的转换思路和差分约束非常像。差分约束处理的是"x - y <= c"这样的不等式，通过建图跑最短路来判断可行性。而这里的乘积型问题处理的是"w1 × w2 × ... > 1"，通过取对数变成"ln(w1) + ln(w2) + ... > 0"，再变成负环检测。
两者的共同点是：都是把原始问题的约束条件转化成图论中的路径/环条件，然后用最短路算法求解。这种"建模-转换-求解"的思路，是图论题目的核心方法论。
5.4 复杂度分析与优化空间
SPFA的平均时间复杂度是O(kE)，其中k是每个节点的平均入队次数，通常很小（一般不超过2）。最坏情况下是O(VE)，但在实际题目中很少达到。
对于这道题，n最多几十，m最多几百，SPFA跑起来非常快。如果数据规模更大，可以考虑用Bellman-Ford的队列优化版本，或者用DFS版本的SPFA（判断负环更快，但容易爆栈）。
DFS版SPFA的思路是：用DFS代替BFS队列，一旦在DFS过程中遇到已经在栈中的节点，就说明存在负环。这种写法在判断负环时通常比BFS版更快，因为它能更快地沿着负环走一圈。但缺点是可能陷入深度递归，需要注意栈溢出。
6. 一些实战中的经验之谈
6.1 关于输入输出的格式
这道题的输入格式是：先读一个整数n，如果n为0则结束；然后读n个货币名称；然后读一个整数m；然后读m行兑换关系，每行的格式是"货币A 汇率 货币B"。
输出格式是"Case X: Yes"或"Case X: No"，注意Case和数字之间有空格，冒号后面也有空格。这些细节看起来不起眼，但格式错误会直接导致WA。
我在第一次提交的时候，就是因为冒号后面少了一个空格，WA了一次。后来养成了一个习惯：先把输出格式在纸上写一遍，确认每个空格和标点都对。
6.2 关于map的性能
对于n <= 30的数据规模，map的性能完全不是问题。但如果你养成了"能用map就用map"的习惯，在数据规模大的题目里可能会被卡常数。这时候可以考虑：
- 用unordered_map代替map（但要注意哈希冲突）
- 先把所有字符串读进来，排序后去重，然后用二分查找代替map
- 用Trie树做字符串到整数的映射
不过对于这道题来说，map是最简单直接的选择，没必要过度优化。
6.3 关于SPFA的"已死"论
网上有个梗叫"SPFA已死"，说的是SPFA的最坏复杂度是O(VE)，在某些精心构造的数据下会被卡成O(VE)。但对于这道题来说，数据规模很小，而且负环检测通常很快就能出结果，所以完全不用担心。
如果你真的担心被卡，可以用Bellman-Ford代替，复杂度稳定在O(VE)。对于n=30，m=900的情况，VE = 27000，完全在可接受范围内。
6.4 关于多组数据的调试技巧
多组数据的题目最容易出的问题就是"上一组数据影响了下一组"。我的调试技巧是：
- 在每组数据开始时，打印一条分隔线，方便区分
- 把关键数组的初始化放在循环内部，而不是外部
- 如果WA了，先检查是不是忘了清空某个全局变量
这道题里需要清空的有：edges数组、map、dist数组、cnt数组、inQueue数组。任何一个忘了清空都可能导致错误。
6.5 一个容易被忽略的细节：自环
如果题目里出现了"USD 1.05 USD"这样的自环，也就是自己兑换自己，汇率大于1，那这本身就是套利机会。SPFA能检测到这种情况吗？
答案是能。因为自环对应一条从u到u的边，权值为-ln(1.05) < 0。在SPFA中，当处理到u时，会发现dist[u] + w < dist[u]，于是更新dist[u]并增加入队次数。如果这个自环的权值为负，那么每次经过都会让dist[u]减小，最终触发负环判定。
所以不需要对自环做特殊处理，SPFA天然支持。
7. 写在最后：这道题教会我的事
做完这道题之后，我最大的收获不是学会了SPFA判断负环，而是理解了一种思维方式：当遇到一个看似新颖的问题时，先想想能不能把它转化成已知问题的形式。汇率套利看起来是金融问题，但转化之后就是标准的负环检测。这种"化归"的能力，比记住多少个算法模板都重要。
另外，这道题也让我意识到，数学变换在算法题里无处不在。取对数把乘法变加法，取负号把大于变小于，这些操作看起来简单，但如果没有想到，就会卡在那里动弹不得。平时多积累一些常用的数学变换技巧，关键时刻能救命。
最后说一个实际比赛中的策略：如果你在赛场上遇到这道题，先花两分钟把模型建好，确认是负环检测，然后直接套模板。不要在现场推导取对数的过程，那是平时训练该做的事。比赛时的时间应该花在调试和验证上，而不是重新发明轮子。
代码写完之后，至少用三组数据测试：一组有套利、一组无套利、一组有自环。三组都过了，基本就能AC。如果WA了，优先检查map的清空和入队次数的判断条件，这两个地方最容易出错。
