企业官网建设流程全解析

1. 这道题到底在问什么

Arbitrage 这个词在金融领域叫“套利”，说白了就是利用不同市场之间的汇率差，低买高卖赚差价。放到编程竞赛里，POJ 2240 这道题给出一组货币和它们之间的汇率，问你能不能通过一系列兑换操作，最终让手里的钱变多。比如你拿 1 美元换成英镑，再换成日元，再换回美元，如果最后手里的美元比一开始多，那就存在套利机会。

这道题的核心不是模拟兑换过程，而是要判断一个图中是否存在“正权环”——也就是一圈走下来，总收益大于 1 的环。因为只要存在这样一个环，你就可以无限次绕着它兑换，财富无限增长。常规做法是把乘法关系转成加法关系，取对数后变成判断负环的问题，然后用 SPFA（Shortest Path Faster Algorithm）来检测。同时因为货币是用字符串表示的，需要用 map 做字符串到整数编号的映射。

适合谁看？如果你正在刷图论专题，已经学过最短路的基础算法，但对“判断负环”和“SPFA 的实际应用”还不太清楚，那这篇内容就是写给你的。我会从建模思路讲到代码实现，再到调试时踩过的坑，尽量把每个细节都摊开说清楚。

2. 从汇率到图论：建模思路拆解

2.1 为什么是“负环”而不是“正环”

题目问的是能不能让钱变多。假设你手里有 1 单位的某种货币，经过一圈兑换后变成 1.05 单位，那这个环的“总倍率”就是 1.05，大于 1，说明存在套利。但如果直接在图里存汇率作为边权，我们要找的就是一个“乘积大于 1 的环”。问题在于，最短路径算法处理的是加法，不是乘法。

这里有一个非常经典的转化技巧：对每条边的汇率取负对数。设汇率为 r，边权 w = -log(r)。那么一圈兑换的总倍率 R = r1 × r2 × ... × rk，取对数后变成 log(R) = log(r1) + log(r2) + ... + log(rk)。如果 R > 1，则 log(R) > 0，那么 -log(R) < 0，也就是说这一圈的总边权是负数。于是“找乘积大于 1 的环”就等价于“找总权值为负的环”，也就是负环。

这个转化是整个解法的基石。我当初第一次看到的时候也觉得有点绕，但拿计算器按两下就明白了：假设汇率是 2，log(2) ≈ 0.693，-log(2) ≈ -0.693，是负数。一圈下来如果总边权是负的，说明总倍率大于 1。

注意：取对数时底数选什么都行，自然对数、以 2 为底、以 10 为底都可以，因为判断的是正负号，底数不影响结论。但代码里一般用 log() 也就是自然对数，写起来最方便。

2.2 为什么选 SPFA 而不是 Bellman-Ford

判断负环的经典算法有两个：Bellman-Ford 和 SPFA。Bellman-Ford 的思路是松弛所有边 V-1 轮，如果第 V 轮还能松弛，就说明存在负环。它的时间复杂度是 O(VE)，对于这道题来说，货币种类 N 最多也就几十，边数最多 N×N，其实 Bellman-Ford 完全够用。

那为什么很多人还是选 SPFA？因为 SPFA 是 Bellman-Ford 的队列优化版本，平均情况下快很多。它的核心思想是：只有被松弛过的点才可能去松弛它的邻居，所以用一个队列维护“待松弛”的点。判断负环的方法是记录每个点的入队次数，如果某个点入队超过 N 次（N 为节点总数），就说明存在负环。

但这里有个细节要注意：SPFA 判断负环有两种常见写法。一种是记录入队次数，超过 N 次就判定负环；另一种是记录最短路径经过的边数，如果某条路径经过的边数达到 N，也说明有负环。两种写法都可以，但入队次数法在实现上更直观一些。

我个人的选择是 SPFA，原因很简单：代码量比 Bellman-Ford 少，而且跑起来通常更快。不过如果你的 SPFA 写得不熟练，用 Bellman-Ford 反而更稳，不容易出错。

2.3 map 在其中的角色

题目里的货币是用三个字母的字符串表示的，比如 USD、GBP、JPY。图论算法需要节点编号，所以必须做一个字符串到整数的映射。C++ 里最自然的选择就是 std::map<string, int>。

每次读入一个货币名，先查 map 里有没有，没有就分配一个新编号。这样最终每个货币对应一个 0 到 N-1 的整数，后续建图和跑 SPFA 都只用整数，效率高也方便。

用 map 的好处是自动去重和排序，不需要手动维护数组。虽然 unordered_map 在理论上更快，但对于这种小规模数据，map 完全够用，而且写法更简洁。我试过用 unordered_map，实际跑下来差别可以忽略不计，所以用哪个都行，看个人习惯。

3. 核心细节与代码实现要点

3.1 数据结构的设计

先明确我们需要哪些数据结构。首先是货币名到编号的映射，用 map<string, int> 搞定。然后是图的存储，因为边数可能比较多，用邻接表比较合适。每个节点存一个 vector，里面放 {目标节点, 边权} 这样的 pair。

边权是 double 类型，因为取对数后是浮点数。这里要特别注意浮点数比较的问题，后面会详细讲。

还需要一个数组 dist[] 来记录从源点到每个点的当前最短距离，初始化为 0 或者一个很大的数。对于判断负环来说，通常的做法是先把所有点的 dist 初始化为 0，然后把所有点都入队。这样做的好处是不需要额外加一个超级源点，而且能检测到图中任意位置的负环，不只是从某个特定源点可达的负环。

入队次数数组 cnt[] 用来记录每个点入队的次数，初始化为 0。队列用 std::queue 就行。

3.2 SPFA 判断负环的完整流程

先把所有点入队，dist 全部设为 0，cnt 全部设为 0，vis 数组标记所有点为“在队列中”。然后开始循环：每次取出队首节点 u，取消它的 vis 标记，遍历它的所有邻居 v。如果 dist[u] + w < dist[v]，就更新 dist[v]，然后检查 v 是否在队列中，如果不在就入队，同时 cnt[v] 加一。如果 cnt[v] >= N，直接返回“存在负环”。

这里有一个容易写错的地方：cnt 是在入队的时候加，不是在松弛的时候加。有些写法是在松弛成功后立刻判断 cnt，但正确的做法应该是入队时累加，因为入队才代表这个点要再次参与松弛。

还有一个细节：初始时把所有点都入队，cnt 应该初始化为 0 还是 1？我见过两种写法。如果初始入队就算一次，那 cnt 初始为 1；如果初始入队不算，那 cnt 初始为 0。两种都能过，但逻辑上要自洽。我一般习惯初始入队不算，cnt 从 0 开始，后续每次入队加一，判断条件是 cnt[v] >= N。

3.3 浮点数比较的坑

这是这道题最容易出问题的地方。因为边权是 double，松弛操作里比较 dist[u] + w < dist[v] 时，浮点误差可能导致本该更新的没更新，或者不该更新的更新了。

举个例子，理论上 dist[u] + w 应该等于 dist[v]，但由于浮点精度问题，可能算出 dist[u] + w = dist[v] - 1e-12，这时候如果直接用 < 比较，就会误判为需要更新，导致多余的松弛，甚至可能影响负环的判断。

解决办法是引入一个极小值 eps，比如 1e-8 或 1e-10。比较时写成 dist[u] + w < dist[v] - eps。这样只有真正更小的时候才更新，避免浮点误差带来的误判。

提示：eps 的选择要根据数据范围来定。这道题的汇率一般不会特别极端，1e-8 足够了。如果 eps 太大，可能漏掉真正的负环；如果太小，又起不到过滤误差的作用。我一般用 1e-8，实测很稳。

另外，判断负环时不需要比较 dist 的大小，只需要看入队次数，所以浮点误差对负环判断的直接影响不大，但会影响松弛的正确性，间接导致入队次数异常。

4. 完整实操流程与代码解析

4.1 输入解析与建图

先看输入格式。每组数据第一行是一个整数 N，表示货币种类数。接下来 N 行每行一个字符串，是货币名称。然后一行一个整数 M，表示兑换关系的数量。接下来 M 行每行两个字符串和一个浮点数，表示从第一种货币到第二种货币的汇率。

读入的时候，每读到一个货币名，就查 map。如果不存在，就分配一个新编号，编号从 0 开始递增。建图的时候，对于每条兑换关系，从源货币到目标货币连一条有向边，边权是 -log(汇率)。

注意这里是有向边，因为汇率是有方向的。A 到 B 的汇率和 B 到 A 的汇率不一定互为倒数，题目给的是单向关系。

#include <iostream> #include <map> #include <queue> #include <vector> #include <cmath> #include <string> using namespace std; const int MAXN = 35; const double EPS = 1e-8; vector<pair<int, double>> graph[MAXN]; double dist[MAXN]; int cnt[MAXN]; bool inQueue[MAXN]; int n, m; bool spfa(int n) { queue<int> q; for (int i = 0; i < n; i++) { dist[i] = 0.0; cnt[i] = 0; inQueue[i] = true; q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (auto &edge : graph[u]) { int v = edge.first; double w = edge.second; if (dist[u] + w < dist[v] - EPS) { dist[v] = dist[u] + w; if (!inQueue[v]) { q.push(v); inQueue[v] = true; cnt[v]++; if (cnt[v] >= n) { return true; } } } } } return false; }

上面这段是核心的 SPFA 代码。初始时把所有点都入队，dist 设为 0，这样等价于加了一个到所有点距离为 0 的超级源点，能检测全图的负环。

4.2 主函数的处理逻辑

主函数里循环读入每组数据，读到 N 为 0 时结束。每组数据先清空 map 和 graph，然后读入 N 个货币名，建立映射。接着读入 M 条兑换关系，建图。最后调用 spfa，根据返回值输出结果。

int main() { int caseNum = 1; while (cin >> n && n != 0) { map<string, int> id; for (int i = 0; i < n; i++) { string name; cin >> name; id[name] = i; graph[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]; double w = -log(rate); graph[u].push_back({v, w}); } bool hasArbitrage = spfa(n); cout << "Case " << caseNum++ << ": "; if (hasArbitrage) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }

注意输入格式里汇率是夹在两个货币名中间的，比如 “USD 0.5 GBP”，读入顺序是 from、rate、to。这个顺序不能搞错，否则边就建反了。

4.3 参数选择与计算过程

边权计算用 -log(rate)。假设 rate = 2.0，log(2.0) ≈ 0.693147，-log(2.0) ≈ -0.693147。如果一圈下来总边权是 -0.1，说明总倍率是 e^0.1 ≈ 1.105，大于 1，存在套利。

eps 选 1e-8。为什么不是 1e-6 或 1e-10？1e-6 可能太大，如果汇率差异很小，真正的负环总权值可能只有 -1e-7，用 1e-6 的 eps 会漏判。1e-10 又可能太小，浮点误差本身就在 1e-15 到 1e-12 量级，1e-10 虽然能过滤大部分误差，但有些累积误差可能达到 1e-11，还是会有影响。1e-8 是一个比较平衡的选择，实测下来既能过滤误差，又不会漏掉真正的负环。

队列用 std::queue，因为 SPFA 是先进先出，不需要优先队列。入队次数上限设为 N，因为一个点最多被松弛 N-1 次，如果入队 N 次，说明有负环。

5. 常见问题与排查技巧实录

5.1 为什么我的 SPFA 一直输出 No

这是最常见的问题。明明手算觉得有套利，程序就是输出 No。排查下来通常有以下几个原因。

第一个原因是边建反了。输入格式是 from rate to，但有些人会习惯性地读成 from to rate，导致汇率对应错误。检查方法很简单，把建图后的边打印出来，看看每条边的方向和权值对不对。

第二个原因是浮点比较的 eps 设得太大。如果 eps 设成 1e-6，而真正的负环总权值只有 -1e-7，那松弛条件 dist[u] + w < dist[v] - eps 就永远不成立，负环检测不到。把 eps 调小到 1e-8 或 1e-10 试试。

第三个原因是初始入队时 cnt 的初始化不对。如果初始入队时 cnt 就设为 1，而判断条件是 cnt[v] >= N，那对于 N=1 的情况可能直接误判。虽然这道题 N 一般大于 1，但逻辑上要统一。

第四个原因是队列清空不彻底。多组数据时，如果队列没有重新初始化，上一组的数据会污染下一组。虽然代码里每次调用 spfa 都重新声明了 queue，但 graph 和 dist 数组要记得清空。

5.2 为什么入队次数判断用 >= N 而不是 > N

这个问题涉及到负环判断的原理。在一个没有负环的图中，任何最短路径最多经过 N-1 条边，也就是最多松弛 N-1 次。如果某个点入队了 N 次，说明它被松弛了至少 N 次，对应的路径经过了至少 N 条边，必然有环，而且是负环。

所以判断条件应该是 cnt[v] >= N，而不是 > N。如果写成 > N，就会多跑一轮，虽然最终结果可能一样，但效率会低一点，而且逻辑上不够严谨。

5.3 多组数据的清空问题

这道题是多组数据，每组数据之间要彻底清空。需要清空的有：map、graph 数组、dist 数组、cnt 数组、inQueue 数组。map 和 graph 在每组开始时重新声明或 clear 就行。dist、cnt、inQueue 在 spfa 函数内部初始化，所以不需要额外清空，但要注意 spfa 函数每次调用时都要重新初始化这些数组。

我踩过的一个坑是：graph 数组用了全局变量，但忘记在每组数据前 clear，导致上一组的边残留，影响了下一组的判断。后来改成在每组数据开始时对每个节点调用 graph[i].clear()，问题就解决了。

5.4 常见问题速查表

注意：如果实在找不到问题，可以把 SPFA 换成 Bellman-Ford 试试。Bellman-Ford 逻辑更简单，不容易出错，虽然慢一点，但对于这道题的数据规模完全够用。用 Bellman-Ford 能过的话，说明问题出在 SPFA 的实现细节上。

5.5 独家避坑技巧

第一个技巧：建图的时候，可以先把所有货币名读进来建立映射，然后再读兑换关系。这样能确保所有货币都有编号，不会出现某个货币在兑换关系里出现但没在货币列表里的情况。虽然题目保证不会这样，但养成这个习惯没坏处。

第二个技巧：如果担心浮点误差，可以在松弛的时候用 dist[u] + w < dist[v] - EPS，但在判断负环的时候不要用 eps，直接用 cnt 判断。因为 cnt 是整数，不受浮点误差影响。

第三个技巧：对于这种小规模数据，其实可以用 Floyd 算法来判断。Floyd 可以求任意两点间的最短路径，跑完之后检查 dist[i][i] 是否小于 0，如果小于 0 就说明有负环。Floyd 的代码更短，只有三重循环，不容易写错。虽然时间复杂度是 O(N^3)，但 N 最大才 30 左右，完全没问题。我有时候赶时间就用 Floyd，稳得很。

第四个技巧：调试的时候可以把 dist 数组打印出来，看看每个点的距离变化。如果某个点的 dist 一直在减小，永远不收敛，那基本就是有负环了。

6. 从这道题延伸出去

6.1 负环检测的通用套路

这道题的核心是负环检测，这个套路在很多题目里都能用。比如判断一个图中是否存在无限循环的收益、检测差分约束系统是否有解、判断最优比率环等等。套路都是一样的：把问题转化成图上的路径权值问题，然后用 SPFA 或 Bellman-Ford 判断负环。

差分约束系统是一个很典型的应用。给定一组形如 x_j - x_i <= c 的不等式，可以建图用最短路求解。如果存在负环，说明不等式组无解。这个转化过程和这道题非常像，都是把代数关系变成图上的边。

6.2 SPFA 的局限性与替代方案

SPFA 虽然平均情况下很快，但最坏情况下的时间复杂度是 O(VE)，和 Bellman-Ford 一样。有些出题人会特意构造数据卡 SPFA，让它退化成 Bellman-Ford 甚至更慢。所以如果题目数据范围很大，或者时间限制很紧，可以考虑用 Bellman-Ford 或者队列优化的 Bellman-Ford。

另外，对于负环检测，还有一种基于 DFS 的 SPFA 写法，递归地进行松弛，一旦发现某个点在当前递归栈中再次被访问，就说明有负环。这种写法在某些图上比 BFS 版的 SPFA 更快，但递归深度可能很大，需要注意栈溢出。

6.3 浮点数图论题的通用注意事项

浮点数图论题有几个通用的坑。第一是精度问题，比较大小一定要用 eps。第二是输出格式，有些题要求保留特定小数位数，要注意。第三是特殊值的处理，比如汇率为 0 或负数的情况，虽然这道题不会出现，但其他题可能会。

还有一个容易忽略的点：如果边权是浮点数，那么最短路径的长度也是浮点数，在判断是否收敛时不能直接用相等比较，要用差值小于 eps 来判断。这道题里 SPFA 的收敛是靠队列为空来判断的，不需要额外判断收敛，但如果是其他算法比如迭代法，就要注意这一点。

6.4 实际应用场景

套利检测在金融领域是真实存在的需求。外汇市场、加密货币市场里，不同交易所之间的汇率差会带来套利机会。当然，现实中的套利还要考虑手续费、滑点、交易延迟等因素，比这道题复杂得多。但核心的图论模型是一样的：把货币当成节点，汇率当成边，找正权环。

除了金融，这种模型还可以用在物流路径优化、网络路由、资源分配等场景。只要问题能转化成“找一条路径使某种累积量超过阈值”，就可以考虑用类似的图论方法。

我个人在实际操作中的体会是，这类题目的难点不在算法本身，而在建模和细节处理。算法都是模板，背下来就行，但怎么把实际问题转化成图论模型，怎么处理浮点误差，怎么调试，这些才是真正考验功底的地方。我刚开始做这道题的时候，SPFA 写了三遍才过，前两遍都是因为 eps 设得不对。后来把 eps 改成 1e-8，一次就过了。所以有时候不是算法不会，而是细节没注意到。

最后再分享一个小技巧：如果实在不确定 eps 设多少，可以先用一个比较小的值比如 1e-10 跑一遍，如果输出 Yes 但你觉得不应该，就调大一点；如果输出 No 但你觉得应该有，就调小一点。多试几次就能找到合适的值。当然，更好的办法是理解浮点误差的来源，从根源上避免问题。