1. 从一道经典题看透套利检测的本质Arbitrage 这个词在金融领域叫“套利”在外汇市场里就是利用不同市场的汇率差低买高卖赚取无风险利润。而 POJ 2240 这道题把套利这件事抽象成了一个图论问题给你若干种货币再给你它们之间的汇率问你有没有可能通过一系列兑换让手里的钱变多。我第一次做这道题的时候脑子里第一反应是“这不就是个找正环的问题吗”。没错但关键在于怎么把“正环”转化成我们熟悉的“负环”模型。这个转化思路才是这道题真正值得琢磨的地方。这道题适合谁看如果你正在学图论、刚接触 SPFA 算法、或者对“判断环”这类问题总是似懂非懂那这道题是一个非常好的练手素材。它不需要你有多深的算法功底但能帮你把 SPFA 判断负环这个知识点吃透顺便练一下 map 的使用。我当年就是靠这道题真正理解了“松弛操作”和“入队次数”之间的关系。接下来我会从整体设计思路开始拆然后讲核心细节、实操过程、常见坑最后给一份可以直接抄的代码模板。整篇内容基于我自己的做题经验和对 SPFA 的理解来写不会照搬任何教科书式的讲解。2. 整体设计思路与方案选型2.1 为什么套利问题能转化成图论问题先把问题翻译一下。假设有 N 种货币给你一张表告诉你 1 单位货币 A 能换多少货币 B。你想知道能不能从某种货币出发经过若干次兑换最后回到这种货币时数量比原来多。举个例子。假设 1 美元换 0.9 欧元1 欧元换 0.8 英镑1 英镑换 1.5 美元。你拿 1 美元换成 0.9 欧元再换成 0.72 英镑再换回美元得到 1.08 美元。你看绕了一圈钱变多了。这就是套利。把这件事画成图每种货币是一个节点汇率是一条有向边边的“权值”就是汇率。那套利就等价于图中存在一个环沿着这个环走一圈边权乘积大于 1。问题来了。我们熟悉的图论算法比如 Bellman-Ford、SPFA处理的是“边权和”的问题不是“边权积”。怎么把乘积变成和取对数。对每条边的汇率 r我们取 -log(r) 作为新的边权。为什么是负的因为原来你要判断的是乘积大于 1取对数之后变成 sum(log(r)) 0再取负号就变成 sum(-log(r)) 0。也就是说原来找“乘积大于 1 的环”现在变成了找“权值和小于 0 的环”也就是负环。这个转化是整个解法的核心。你可能会问为什么不直接比较乘积因为 SPFA 的松弛操作是基于加法的你没法直接在里面做乘法比较。取对数之后所有的数学工具都能用上了。注意取对数的时候要用 double而且精度问题要小心。一般取到 1e-8 左右的误差范围就够了但有些题目卡精度需要根据实际情况调整。2.2 为什么选 SPFA 而不是 Bellman-Ford 或 Floyd判断负环有三种常见做法Bellman-Ford、SPFA、Floyd。Bellman-Ford 是最朴素的对所有边做 N-1 轮松弛第 N 轮如果还能松弛就说明有负环。时间复杂度 O(VE)对于这道题的数据量来说完全够用。但它的缺点是每一轮都要遍历所有边很多边其实已经稳定了还在重复检查效率上有浪费。Floyd 是 O(N^3)这道题 N 最大也就 30 左右其实也能过。但 Floyd 判断负环的方式是看 dist[i][i] 是否小于 0这个思路也对但写起来三重循环而且如果 N 稍微大一点就吃不消了。SPFA 是 Bellman-Ford 的队列优化版本。它只把“被松弛过的节点”重新入队避免了大量无效遍历。判断负环的方式是记录每个节点的入队次数如果某个节点入队超过 N 次就说明存在负环。为什么是 N 次因为在一个没有负环的图中每个节点最多被松弛 N-1 次对应的入队次数也不会超过 N-1。一旦超过 N就说明有环在反复松弛。我选 SPFA 的理由很简单代码比 Bellman-Ford 简洁效率比 Floyd 高而且入队计数的判断方式非常直观。对于这道题来说SPFA 是最平衡的选择。2.3 map 在其中的角色与选型考量这道题的输入是货币名称比如 “USD”、“EUR” 这种字符串。但图论算法处理的是节点编号是整数。所以需要一个映射关系把字符串映射成 0 到 N-1 的整数。mapstring, int 是最自然的选择。每次读入一个货币名称先查 map 里有没有没有就分配一个新编号。这样既完成了映射又顺便统计了货币种类数。为什么不用 unordered_map理论上 unordered_map 的查询是 O(1)map 是 O(log N)。但这道题 N 很小log N 几乎可以忽略不计。而且 map 的代码更简洁不需要额外处理哈希冲突。所以用 map 就够了。也有人用字典树或者手写哈希但对于这道题来说完全是杀鸡用牛刀。选型的原则是够用就好不要为了炫技增加代码复杂度。3. 核心细节解析与实操要点3.1 汇率取对数的数学原理与精度处理前面说了要把汇率 r 转化成 -log(r)。这里展开讲一下为什么。假设你有一系列汇率 r1, r2, ..., rk沿着环走一圈最终得到的倍数是 r1 * r2 * ... * rk。你要判断这个乘积是否大于 1。两边同时取自然对数log(r1 * r2 * ... * rk) log(r1) log(r2) ... log(rk)。如果乘积大于 1那么对数和大于 0。再取负号-log(r1) - log(r2) - ... - log(rk) 0。这就是负环的定义。所以每条边的权值就是 -log(r)。在代码里就是 -log(rate)注意要用 double 类型。精度方面log 函数的计算结果本身就有浮点误差。在判断负环的时候不能用 dist[v] dist[u] w 这种严格小于而应该用 dist[v] dist[u] w eps 这种带容差的方式。eps 一般取 1e-8 或者 1e-9。我实测下来这道题的测试数据对精度要求不算特别苛刻1e-8 的 eps 就能过。但如果你在别的平台上做类似的题可能需要调整。一个经验法则是如果 WA 了但思路没问题先把 eps 调大一个数量级试试。3.2 SPFA 判断负环的入队计数逻辑SPFA 的核心是一个队列。初始时把源点入队然后不断取出队首节点对它所有邻接边做松弛。如果某条边能松弛成功就把对应的邻接节点入队如果它不在队列里。判断负环的关键在于记录每个节点的入队次数 cnt[v]。每次节点 v 入队时cnt[v]。如果 cnt[v] N就说明存在负环。为什么是 N因为在一个有 N 个节点的图中如果不存在负环从源点到任意节点的最短路径最多经过 N-1 条边。每经过一条边最多导致一次松弛。所以每个节点最多被松弛 N-1 次入队次数也不会超过 N-1。一旦达到 N就说明有节点被反复松弛必然存在负环。这里有一个细节源点的初始入队算不算一次算。所以源点的 cnt 初始为 1。或者你也可以把所有节点都初始入队cnt 都设为 1这样相当于加了一个超级源点能检测整个图里任意位置的负环。对于这道题来说因为图不一定连通所以把所有节点都入队是更稳妥的做法。实操心得如果你只从第一个节点开始 SPFA可能会漏掉不连通部分的负环。把所有节点初始入队cnt 都设为 1可以一次性检测全图。3.3 图的存储方式与边的组织这道题用邻接表存图最合适。N 最多 30边最多 N*(N-1) 条用 vector 或者链式前向星都行。我用的是 vector 套结构体struct Edge { int to; double w; }; vectorEdge adj[MAXN];每次读入一条汇率比如 “USD EUR 0.9”就找到 USD 和 EUR 的编号 u 和 v然后 adj[u].push_back({v, -log(0.9)})。注意是有向边。因为汇率是有方向的1 美元换 0.9 欧元不代表 1 欧元换 1/0.9 美元虽然实际市场上差不多是这样但题目给的数据不一定满足这个关系。所以每条汇率信息只加一条有向边。如果题目给的是一对多的关系比如 “USD 0.9 EUR” 这种格式那就要看清楚输入格式再决定怎么解析。POJ 2240 的输入格式是先给一个整数 N然后 N 行每行一个货币名称然后一个整数 M然后 M 行每行 “货币A 汇率 货币B”。这个格式要记清楚不然读入就会出错。3.4 初始化与多组数据的处理这道题是多组数据每组数据以 N0 结束。所以主函数里要有一个 while 循环每次读入 N如果 N0 就 break。每组数据开始前要清空 map、清空邻接表、重置所有数组。这些清理工作看起来简单但很容易漏。我当年就因为忘了清空 map导致第二组数据的货币编号跟第一组混在一起调了半天才发现。建议把每组数据的处理封装成一个函数或者至少在循环开头把所有需要重置的变量都列出来检查一遍。map 用 clear()邻接表用 clear()dist 数组重新赋值为 0因为要找负环初始距离设为 0 比较方便cnt 数组全部设为 1如果所有节点初始入队的话。4. 完整实操过程与核心代码实现4.1 输入解析与货币编号映射先看输入部分。POJ 2240 的输入大概是这样的3 USD EUR GBP 3 USD EUR 0.9 EUR GBP 0.8 GBP USD 1.5 0第一行是货币种类数 N。接下来 N 行是货币名称。然后一个整数 M 表示汇率条目数。接下来 M 行每行三个部分源货币、目标货币、汇率。解析的时候用一个 mapstring, int 来存货币名称到编号的映射。每读到一个货币名称如果 map 里没有就分配一个新编号。mapstring, int id; int cnt_id 0; for (int i 0; i N; i) { string name; cin name; if (id.find(name) id.end()) { id[name] cnt_id; } }然后读 M 条汇率int M; cin M; for (int i 0; i M; i) { string a, b; double rate; cin a rate b; int u id[a]; int v id[b]; adj[u].push_back({v, -log(rate)}); }注意输入顺序是 “货币A 汇率 货币B”不是 “货币A 货币B 汇率”。这个顺序如果搞反了读入的数据就全乱了。我建议在读入之前先仔细看一遍题目给的样例输入确认每个字段的位置。4.2 SPFA 主循环与负环判定SPFA 的主循环逻辑如下bool spfa(int n) { queueint q; vectordouble dist(n, 0.0); vectorint cnt(n, 1); vectorbool inq(n, true); for (int i 0; i n; i) { q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto e : adj[u]) { int v e.to; double w e.w; if (dist[v] dist[u] w 1e-8) { dist[v] dist[u] w; cnt[v]; if (cnt[v] n) { return true; } if (!inq[v]) { q.push(v); inq[v] true; } } } } return false; }几个关键点第一dist 数组初始化为 0。因为我们要找的是负环初始距离设为 0 相当于假设每个节点一开始的距离都是 0然后看能不能通过松弛让某个节点的距离变成负数。如果有负环沿着环走一圈距离会不断减小最终触发入队次数超限。第二cnt 数组初始化为 1因为所有节点一开始都入队了。如果只从单个源点开始那源点的 cnt 设为 1其他设为 0。第三松弛条件用的是dist[v] dist[u] w 1e-8。这里的 1e-8 是精度容差。如果不加这个容差浮点误差可能导致本该松弛的边没有被松弛或者不该松弛的边被反复松弛。第四一旦 cnt[v] n直接返回 true不需要继续跑完。这是一个优化能提前结束。4.3 输出格式与多组数据的收尾每组数据的输出格式是Case 1: Yes Case 2: No注意 Case 后面有一个空格冒号后面也有一个空格。这种格式细节很容易被忽略但 POJ 的评测是严格匹配的格式错了就是 Presentation Error 或者 Wrong Answer。我一般会在代码里这样写cout Case case_num : (has_arbitrage ? Yes : No) endl;case_num 从 1 开始每组数据结束后递增。多组数据的循环结构int case_num 1; while (cin N N ! 0) { // 清空全局变量 id.clear(); for (int i 0; i MAXN; i) adj[i].clear(); // 读入货币名称 // 读入汇率 // 跑 SPFA // 输出结果 case_num; }清空操作一定要放在每组数据的开头不要放在结尾。因为如果放在结尾最后一组数据结束后还会多清一次虽然不影响结果但逻辑上不够清晰。5. 常见问题与排查技巧实录5.1 为什么我的 SPFA 判断负环总是误判这是最常见的问题。SPFA 判断负环误判通常有三个原因。第一个原因是精度容差没设对。如果你用的是dist[v] dist[u] w这种严格比较浮点误差可能导致本来不应该松弛的边被松弛了从而误判负环。解决办法是加一个 eps比如 1e-8。第二个原因是入队次数的阈值设错了。有人把阈值设成 N-1有人设成 N有人设成 N1。正确的阈值是 N。因为无负环时每个节点最多入队 N-1 次达到 N 就说明有负环。如果你设成 N-1可能会把一些边界情况误判为负环。第三个原因是初始入队策略不对。如果你只从第一个节点开始 SPFA但负环在另一个不连通的部分那就检测不到。解决办法是把所有节点都初始入队cnt 都设为 1。5.2 取对数之后结果不对怎么办取对数之后结果不对通常是两个原因。一是 log 的底数搞混了。我用的是自然对数 log()也就是以 e 为底。你用 log2() 或者 log10() 也行只要前后一致就可以。因为判断的是乘积是否大于 1取任何底数的对数符号判断都是一样的。二是取负号的位置搞错了。正确的做法是对每条边的汇率取 -log(r)。如果你忘了取负号那就变成了找正环判断条件也要反过来。我建议在代码里写一个注释标明这条边的权值是 -log(rate)免得后面自己看糊涂。5.3 map 使用中的坑与性能考量map 用起来简单但有几个坑要注意。第一个坑是 map 的默认值。如果你用id[name]来访问一个不存在的键map 会自动插入一个默认值 0。这会导致你的编号分配逻辑出错。正确的做法是先用find()检查不存在再插入。第二个坑是 map 的清空。多组数据之间一定要 clear()否则上一组的映射会残留到下一组。第三个坑是性能。虽然这道题 N 很小map 的性能完全够用但如果你在别的题里遇到 N 很大的情况map 的 O(log N) 查询可能会成为瓶颈。那时候可以考虑用 unordered_map 或者手写哈希。5.4 常见问题速查表问题现象可能原因排查方法解决方案结果全是 No取对数后忘了取负号检查边权计算改为 -log(rate)结果全是 Yes精度容差太大检查 eps 值减小 eps 到 1e-8第二组数据开始出错map 或邻接表没清空检查循环开头加 clear() 操作编译错误忘了包含 cmath 头文件检查 include加 #include运行超时SPFA 没有提前退出检查 cnt 判断cntn 时立即 return输出格式错误Case 后面少了空格对比样例输出严格按格式输出避坑技巧如果你实在找不到问题可以把中间结果打印出来。比如打印每个节点的 dist 和 cnt看看 SPFA 的执行过程是否符合预期。这个方法虽然笨但非常有效。6. 从这道题延伸出的通用解题模板6.1 判断负环的 SPFA 模板把这道题的解法抽象一下可以得到一个通用的 SPFA 判断负环模板bool spfa_negative_cycle(int n, vectorEdge adj[]) { queueint q; vectordouble dist(n, 0.0); vectorint cnt(n, 1); vectorbool inq(n, true); for (int i 0; i n; i) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto e : adj[u]) { int v e.to; double w e.w; if (dist[v] dist[u] w 1e-8) { dist[v] dist[u] w; cnt[v]; if (cnt[v] n) return true; if (!inq[v]) { q.push(v); inq[v] true; } } } } return false; }这个模板可以直接套用到任何判断负环的题目上。只需要根据题目要求调整边权的计算方式和精度容差。6.2 乘积型环问题的通用转化思路这道题的核心转化思路是乘积型环问题可以通过取对数转化成和型环问题。具体来说如果你要判断的是“环上边权乘积大于 1”就取 -log 变成“环上边权和小于 0”也就是负环。如果你要判断的是“环上边权乘积小于 1”就取 log 变成“环上边权和小于 0”也是负环。如果你要判断的是“环上边权乘积等于 1”那就取 log 变成“环上边权和等于 0”这是零环问题需要另外处理。这个转化思路不仅适用于汇率套利还适用于很多其他场景比如化学反应中的物质守恒、电路中的增益计算等等。只要涉及到连乘关系的环判断都可以考虑取对数。6.3 浮点数比较的通用原则浮点数比较是算法题里的一个老大难问题。我的经验是第一永远不要用 比较两个浮点数。要用 fabs(a - b) eps 的方式。第二eps 的选择要根据题目要求来。一般来说 1e-8 是一个比较安全的默认值。如果题目对精度要求高可以取 1e-9 或 1e-10。如果题目数据范围大可以适当放宽到 1e-6。第三在松弛操作中比较条件要写成dist[v] dist[u] w eps而不是dist[v] dist[u] w。这样能避免因为浮点误差导致的误松弛。第四如果实在不确定 eps 取多少可以先用 1e-8 试一下如果 WA 了就调整。有时候把 eps 调大一点反而能过因为题目数据可能本身就有误差。7. 我个人在实际操作中的体会这道题我前前后后做了三次才彻底搞明白。第一次是没想清楚怎么把乘积转化成和第二次是精度问题导致误判第三次是忘了清空 map 导致多组数据出错。每次踩坑都让我对 SPFA 和浮点数处理有了更深的理解。我现在做这类题的习惯是先把数学转化想清楚写在纸上确认无误再开始写代码。代码写完之后先用题目给的样例测一遍再用自己构造的边界数据测一遍。比如这道题我会构造一个没有套利机会的图看看输出是不是 No再构造一个有明显套利机会的图看看输出是不是 Yes。还有一个经验是不要怕用 double。有些同学觉得浮点数不精确想用整数或者分数来表示汇率。但在这道题里汇率本身就是小数用 double 是最自然的选择。只要精度容差设对了double 完全够用。最后分享一个小技巧如果你在本地跑的结果和评测结果不一致先检查一下是不是多组数据的清空没做好。这个问题太常见了我至少遇到过五六次。清空操作虽然简单但很容易在写代码的时候忽略掉。