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-FordO(VE)边数较少时可用可以但不必要FloydO(V³)需要全源最短路时不推荐杀鸡用牛刀SPFA平均O(kE)最坏O(VE)稀疏图、负环检测推荐这道题的图通常是稀疏图货币种类不多兑换关系也不会太密集SPFA的平均性能很好。而且SPFA的负环检测逻辑非常直观如果一个节点入队次数超过n-1次说明存在负环。这个判据的数学依据是在没有负环的情况下任何节点的最短路径最多经过n-1条边对应最多被松弛n-1次。如果超过了必然是因为负环导致路径可以无限缩短。2.4 map在这里扮演什么角色题目给的是货币名称比如USD、EUR、GBP这样的字符串但图论算法处理的是整数编号。所以我们需要一个从字符串到整数的映射。mapstring, int就是干这个的。为什么不用哈希表因为map在C里是有序的而且对于这道题的数据规模来说map的性能完全够用。更重要的是map的用法简单直观不需要手写哈希函数不容易出错。当然如果你追求极致性能用unordered_map也可以但要注意unordered_map在某些评测环境下可能因为哈希冲突被卡常数。我在实际写的时候习惯用mapstring, 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次。如果第n1次入队就说明有负环。不过不同人的写法略有差异有的人判断入队次数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; }; vectorEdge edges[MAXN]; double dist[MAXN]; int cnt[MAXN]; // 入队次数 bool inQueue[MAXN]; int n, m; bool spfa() { queueint 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; mapstring, 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条边的最短路径第n1次入队就说明有负环。4.4 坑四map的清空问题在多组数据的题目里map必须在每组数据开始时清空。我有一次忘了清空导致上一组的货币名称映射残留下来新的一组数据里出现了错误的编号对应结果WA了好几次。正确的做法是在每组数据开始时重新声明一个map或者调用map.clear()。我倾向于在循环内部重新声明这样更安全。4.5 坑五浮点数比较的精度问题虽然这道题对精度不敏感但在某些变体题目里浮点误差可能导致误判。比如两个非常接近的汇率取对数后差值极小可能因为浮点误差导致松弛条件判断错误。解决方案是加一个EPSif (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)。对于n30m900的情况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的清空和入队次数的判断条件这两个地方最容易出错。 
长河君 · 2026/10/15 1:19:09 · 阅读 1.2k SPFA负环检测实战：汇率套利问题中的图论建模与map映射
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-FordO(VE)边数较少时可用可以但不必要FloydO(V³)需要全源最短路时不推荐杀鸡用牛刀SPFA平均O(kE)最坏O(VE)稀疏图、负环检测推荐这道题的图通常是稀疏图货币种类不多兑换关系也不会太密集SPFA的平均性能很好。而且SPFA的负环检测逻辑非常直观如果一个节点入队次数超过n-1次说明存在负环。这个判据的数学依据是在没有负环的情况下任何节点的最短路径最多经过n-1条边对应最多被松弛n-1次。如果超过了必然是因为负环导致路径可以无限缩短。2.4 map在这里扮演什么角色题目给的是货币名称比如USD、EUR、GBP这样的字符串但图论算法处理的是整数编号。所以我们需要一个从字符串到整数的映射。mapstring, int就是干这个的。为什么不用哈希表因为map在C里是有序的而且对于这道题的数据规模来说map的性能完全够用。更重要的是map的用法简单直观不需要手写哈希函数不容易出错。当然如果你追求极致性能用unordered_map也可以但要注意unordered_map在某些评测环境下可能因为哈希冲突被卡常数。我在实际写的时候习惯用mapstring, 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次。如果第n1次入队就说明有负环。不过不同人的写法略有差异有的人判断入队次数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; }; vectorEdge edges[MAXN]; double dist[MAXN]; int cnt[MAXN]; // 入队次数 bool inQueue[MAXN]; int n, m; bool spfa() { queueint 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; mapstring, 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条边的最短路径第n1次入队就说明有负环。4.4 坑四map的清空问题在多组数据的题目里map必须在每组数据开始时清空。我有一次忘了清空导致上一组的货币名称映射残留下来新的一组数据里出现了错误的编号对应结果WA了好几次。正确的做法是在每组数据开始时重新声明一个map或者调用map.clear()。我倾向于在循环内部重新声明这样更安全。4.5 坑五浮点数比较的精度问题虽然这道题对精度不敏感但在某些变体题目里浮点误差可能导致误判。比如两个非常接近的汇率取对数后差值极小可能因为浮点误差导致松弛条件判断错误。解决方案是加一个EPSif (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)。对于n30m900的情况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的清空和入队次数的判断条件这两个地方最容易出错。