企业官网建设流程全解析

1. Arbitrage 这道题在考什么：先把题意翻译成人话

1.1 输入输出长什么样

题目编号 2240，名字叫 Arbitrage，是一道非常经典的图论题。它的输入是典型的多组测试数据结构：每组数据第一行是一个整数 n 表示货币种类数，接下来 n 行是货币名称；紧接着一行是整数 m 表示汇率条目数，再后面 m 行，每行是一个"货币A 汇率 货币B"的三元组，意思是 1 单位货币A 可以兑换成 rate 单位货币B；当你读到单独的一个 0 时，整个输入结束。输出就是按照测试组数依次打印Case 1: Yes或者Case 1: No，每组占一行。

拿一个最小例子说明：假设有三种货币 u、v、w，汇率给三条：u→v 是 0.5，v→w 是 10.0，w→u 是 0.21。你拿 1 个 u 先换 0.5 个 v，再换 5 个 w，最后换回 1.05 个 u，净赚 0.05。所以答案是 Yes。注意这里每一条汇率单独看都在"亏钱"或持平，但连成一个环之后反而赚钱了，这就是套利问题最核心的矛盾点。

1.2 三个容易被忽略的题目细节

第一，汇率是有向的。u→v 给的是 0.5，不代表 v→u 就是 2.0，题目里两个方向的汇率必须分别给出，你不能自己用倒数去补。第二，兑换次数没有上限，这意味着你不能把题目当成单源最短路或者"找一条简单路径"来处理，你要找的是环。第三，数据范围不大：n 通常不超过 30，m 可以到 n^2 级别，所以 O(n*m) 的 Bellman-Ford 绰绰有余，甚至 O(n^3) 的算法在很多情况下也能过，但这不意味着你可以不搞懂为什么标准解法是 Bellman-Ford。

我见过不少新手第一次读题会纠结"要不要记录每个货币持有量是多少"，看到"兑换次数不限"又想着用 BFS 分层图或者迭代加深。其实都不用。题目只问你"是否存在套利机会"，不问你最优能赚多少，也不要求输出兑换序列，所以本质上就是一个纯粹的环判定问题。

1.3 从汇率表到带权有向图

把每种货币看成一个顶点，每条汇率看成一条从源货币指向目标货币的带权有向边，一次完整的兑换过程就对应图上的一个有向环，总收益就是环上所有汇率的乘积。于是整个问题被翻译成一句图论语言：是否存在一个环，其边权乘积严格大于 1？做到这一步，题目已经从"金融直觉"变成了一道赤裸裸的图论判断题。

2. 建模思路：把"乘积大于 1"改写成"存在负环"

2.1 先用数学写清楚判定条件

假设有一个环 v1 → v2 → ... → vk → v1，对应的汇率是 r1, r2, ..., rk。从 1 单位 v1 出发，绕一圈回到 v1 时，你持有的数量是：

amount = r1 × r2 × ... × rk

存在套利机会，等价于这个乘积大于 1。问题在于，绝大多数图算法最顺手的度量是"路径权值之和"，而不是"路径权值之积"。直接拿乘积去套最短路算法，算法根本不知道怎么比较两条路径的优劣。所以要做一层数学变换。

2.2 取负对数：把乘法拆成加法

对乘积两边取自然对数：ln(amount) = ln(r1) + ln(r2) + ... + ln(rk)。因为 amount > 1 等价于 ln(amount) > 0，所以判定条件变成：

ln(r1) + ln(r2) + ... + ln(rk) > 0

再整体取一个负号，就得到：

(-ln(r1)) + (-ln(r2)) + ... + (-ln(rk)) < 0

也就是说，如果定义每条有向边 u→v 的权值 w = -ln(rate)，那么一个环是"套利环"，当且仅当这个环的权值和是负数。这不就是最短路理论里最经典的负环定义吗？很多资料上来就说"取负对数然后套 Bellman-Ford"，但不解释为什么。上面的推导就是全部理由：取对数把乘法变加法，取负号把"乘积大于 1"变成"环权和小于 0"，而"环权和小于 0"正是负环检测的标准输入。

拿前面那个例子验算一下：ln(0.5) ≈ -0.693，ln(10) ≈ 2.302，ln(0.21) ≈ -1.561，三者和为 0.048，大于 0，确实存在套利。取负号之后，三条边的权值分别是 0.693、-2.302、1.561，环权和是 -0.048，小于 0，负环成立。

2.3 为什么 Dijkstra 不行，Floyd 能用但不够通用

Dijkstra 的前提是边权非负，但负对数转换之后边权有正有负（rate > 1 时 -ln(rate) < 0，rate < 1 时反而大于 0），Dijkstra 的贪心性质在负权边存在时会直接崩溃，而且它本身也没有"检测负环"这个说法。

Floyd-Warshall 倒是能做。把 f[i][j] 定义为从货币 i 换到货币 j 能拿到的最大倍数，初始化 f[i][i] = 1，读入一条 u→v 的汇率 r 就令 f[u][v] = r，然后跑三重循环做乘法松弛：f[i][j] = max(f[i][j], f[i][k] * f[k][j])，最后检查是否存在 f[i][i] > 1。这个写法对 n ≤ 30 完全可行，代码甚至更短。但它的 O(n^3) 复杂度在 n 变大时就不够看了，而且它对"环的检测"这件事没有 Bellman-Ford 那么干脆。

Bellman-Ford 的优势在于三点：第一，它能处理负权边；第二，它的松弛轮数天然绑定"路径不能经过同一个点超过一次"这个性质，n-1 轮跑完再做一次额外扫描，就能把负环揪出来；第三，它的复杂度 O(n*m) 对这类小图几乎可以忽略不计。所以这道题的标准解法和大部分题解选 Bellman-Ford，不是因为它代码最短，而是因为它是一把能解决一整类问题的通用钥匙。

3. Bellman-Ford 检测负环的完整实现

3.1 建图：字符串货币名的编号映射

货币名是字符串，算法只认整数下标，第一步要用 map 做字符串到编号的映射。建图和读入部分的代码骨架如下：

#include <bits/stdc++.h> using namespace std; struct Edge { int u, v; double w; // -ln(rate) }; int main() { int n, m, cas = 1; while (cin >> n && n) { map<string, int> id; string name; for (int i = 0; i < n; ++i) { cin >> name; id[name] = i; } cin >> m; vector<Edge> edges; string a, b; double rate; for (int i = 0; i < m; ++i) { cin >> a >> rate >> b; edges.push_back({id[a], id[b], -log(rate)}); } // 负环检测逻辑见下 } return 0; }

这里有一个容易写错的点：id[a]用的是 map 的 operator[]，如果货币名不存在，它会自动插入一个默认值 0。本题保证所有货币名都出现过，所以直接这么用没问题；但如果换成别的题目，建议先用 find 判断是否存在，避免把没出现过的名字误映射成 0，导致建图错乱且极难排查。

3.2 初始化：为什么所有 dist 都置 0 而不是 INF

标准的单源 Bellman-Ford 会把所有 dist 初始化为 INF，再把源点 dist 设为 0。但这题我们检测的是"图中任意位置是否存在负环"，不是"从某个固定货币出发能不能越换越少"。解决办法是把所有顶点的 dist 全部初始化为 0。

解释一下为什么这样做可行。每一轮松弛，dist[v] 会被更新成它当前能到达的、权值和最小的路径权值。把所有顶点初始化为 0，相当于给每个点都安排了一个虚拟的、权值为 0 的入口，任何负权边一旦出现，就会立刻被吸收进 dist 里。如果某个负环存在，环上的点在每一轮松弛之后 dist 都会继续下降，这种下降不可能在有限轮内结束。换句话说，dist 全部置 0 等于把所有可能成为套利起点的货币都提前"免费激活"了，负环无处可藏。

提示：如果你真的想从某个固定源点出发检测负环，那就老老实实把 dist 初始化为 INF 再置 dist[s] = 0。两种初始化对应两种问题语义，别混用。

3.3 松弛 n-1 轮再加第 n 轮扫描

负环检测的骨架就三段：n-1 轮松弛、第 n 轮扫描、输出结果。

vector<double> dist(n, 0.0); for (int k = 0; k < n - 1; ++k) { for (const auto &e : edges) { if (dist[e.v] > dist[e.u] + e.w + 1e-9) { dist[e.v] = dist[e.u] + e.w; } } } bool hasNegativeCycle = false; for (const auto &e : edges) { if (dist[e.v] > dist[e.u] + e.w + 1e-9) { hasNegativeCycle = true; break; } } cout << "Case " << cas++ << ": " << (hasNegativeCycle ? "Yes" : "No") << endl;

为什么只需要 n-1 轮？因为在一个没有负环的图里，任意一条最短路径最多经过 n-1 条边；如果一条路径经过了 n 条边甚至更多，那么路径里必然出现了重复顶点，也就必然存在环，而正环会让总权值变大、没有保留的必要。所以 n-1 轮松弛之后，所有真正的最短距离都已经收敛。这时候再扫描所有边，如果仍有一条边能满足松弛条件，唯一的解释就是存在一个能让总权值无限变小的环——负环。

这里我用了+ 1e-9这个阈值，目的是避免 double 比较时因为浮点误差把"恰好相等"误判成"还能松弛"。eps 的方向要写对：只有当下一个新的候选值严格小于当前值、并且差距超过精度阈值时才更新。

3.4 完整可用的 AC 参考代码

把前面的内容拼起来，就是一个可以直接提交的最小实现，完整版如下：

#include <bits/stdc++.h> using namespace std; struct Edge { int u, v; double w; }; int main() { int n, m, cas = 1; while (cin >> n && n) { map<string, int> id; string name; for (int i = 0; i < n; ++i) { cin >> name; id[name] = i; } cin >> m; vector<Edge> edges; string a, b; double rate; for (int i = 0; i < m; ++i) { cin >> a >> rate >> b; edges.push_back({id[a], id[b], -log(rate)}); } vector<double> dist(n, 0.0); for (int k = 0; k < n - 1; ++k) { for (const auto &e : edges) { if (dist[e.v] > dist[e.u] + e.w + 1e-9) { dist[e.v] = dist[e.u] + e.w; } } } bool arbitrage = false; for (const auto &e : edges) { if (dist[e.v] > dist[e.u] + e.w + 1e-9) { arbitrage = true; break; } } cout << "Case " << cas++ << ": " << (arbitrage ? "Yes" : "No") << endl; } return 0; }

这个实现的核心逻辑就是负环检测的标配写法，复杂度为 O(n*m)，对本题的数据量完全无压力。编译时记得开 C++11 或更高版本，bits/stdc++.h和花括号初始化的 struct 需要编译器支持。

4. 实测踩坑与调试经验

4.1 最阴间的坑：汇率不是对称的

有一类用例很迷惑人：它给出的汇率在数值上"看起来是对称的"，比如 u→v 是 0.5，v→u 正好是 2.0，但即便如此，环上有三条或更多条边时，乘积效应是局部对称看不出来的。更常见的坑是：题目给的两个方向汇率并不互为倒数，如果你偷懒在代码里只存一条边，另一个方向用 1/rate 补上，那就完全错了。老老实实按输入建边，一个方向存一条，不要自己"脑补"对称关系。

4.2 网上两个流派：dist 初始化为 1 还是 0

这题你能搜到两种做法。一种就是本文的负对数转换，dist 初始化为 0，检测负环。另一种不取 log，直接定义"从任意货币出发经过若干次兑换能持有的最大数量"，dist 初始化为 1.0，松弛时做dist[v] = max(dist[v], dist[u] * rate)，n-1 轮后检查是否还能增大，也就是检测"正环"。两派都能 AC。

如果你混着看资料，最容易翻车的地方就是把负对数边的代码和乘积松弛的代码混在一起。比如已经用 -log(rate) 建边了，松弛语句却写成if (dist[v] < dist[u] * rate)，那结果必然乱套。认准一条路：要么统一"加法加负环检测"，要么统一"乘法加正环检测"，别两边各抄一半。

4.3 浮点精度：要不要加 eps，加多少

题目里的汇率一般保留两位小数，按理论值算完，double 的比较通常不会出现恰好卡在边界上的情况。但负对数运算本身有舍入误差，比如 rate = 1.0001 时 -ln(rate) 大约是 -0.00009999，和 0 的差别非常小，如果不加 eps，而数据又故意构造了这种边界，你就可能把 No 判成 Yes。我的习惯是统一加 1e-9。但阈值不能开得太大，否则会把真正微弱的负环漏掉；对本题的数据量来说，1e-9 是一个安全值。

4.4 多组测试数据的三个常见事故

第一个事故是忘了在每组数据开头清空 edges 容器。如果你把 vector 声明在 while 循环内部，就不会有这个问题；但要是把容器声明在循环外面复用，务必记得 clear。第二个事故是 case 计数变量忘了自增，导致所有输出都变成 Case 1。第三个事故是输入结束条件处理错：这题是读到 n = 0 就终止，不是读到 EOF，也不存在一个独立的测试数量 T，第一次写的人很容易照习惯去先读一个 T。

4.5 用自环做冒烟测试

如果你不确认自己的模板对不对，可以手造一组最平凡的数据验证：1 种货币，1 条自环，汇率 2.0。这显然是套利，1 变 2，2 变 4，无限翻倍。负对数写法下边权是约 -0.693，dist[0] 初始为 0，第一轮松弛就把它更新成 -0.693，第二轮继续下降，最后一轮扫描依然能松弛，于是输出 Yes。这个自环用例是我每次写完负环模板后的第一个冒烟测试，五分钟内就能确认初始化、松弛、判定三段逻辑是否都正常。

5. 从 Arbitrage 延伸出去的环判定套路

5.1 无 log 版本：直接做乘积松弛

如果觉得对数转换有点绕，完全可以不取 log。把 dist 的含义改成"从任意货币出发，经过若干次兑换后能持有的最大数量"，初始化为 1.0，松弛时用乘法更新：

vector<double> money(n, 1.0); for (int k = 0; k < n - 1; ++k) { for (const auto &e : edges) { if (money[e.v] < money[e.u] * e.rate - 1e-12) { money[e.v] = money[e.u] * e.rate; } } } bool arbitrage = false; for (const auto &e : edges) { if (money[e.v] < money[e.u] * e.rate - 1e-12) { arbitrage = true; break; } }

注意这里的 eps 方向：只有当下一个候选值严格大于当前值并且超出精度阈值时才更新，也就是money[e.u] * e.rate - money[e.v] > eps，等价于上面写的不等式。n-1 轮后如果还有边能让 money 继续增大，说明存在乘积大于 1 的正环，套利成立。

两种写法比较下来，乘积形式更贴近题意，不引入 log 的近似误差；但它在思想上依然是 Bellman-Ford 的松弛框架，"能改善就更新，更新 n-1 轮之后还能改善则存在环"。想通这一点，你就不会再纠结"这题到底算不算 Bellman-Ford"了。

5.2 Floyd 方案：换一个视角看同一道题

顺手提一下 Floyd 写法，因为它是很好的复习素材。设 f[i][j] 为从货币 i 换成货币 j 能拿到的最大倍数，初始化 f[i][i] = 1，每读入一条 u→v 的汇率 r 就令 f[u][v] = r，然后跑三重循环：

for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (f[i][j] < f[i][k] * f[k][j]) f[i][j] = f[i][k] * f[k][j];

结束后检查有没有 f[i][i] > 1。这个写法更短，但复杂度是 O(n^3)。n=30 时跑起来毫无压力，一旦 n 到几百，三重循环就跑不动了。所以掌握 Bellman-Ford 版本，本质上是在为更通用的负环检测打基础，Floyd 版本更适合当作思维训练而不是日常武器。

5.3 把负环检测当成通用武器

Arbitrage 只是负环检测这个模型里的一朵浪花。同一套思想还能用在很多地方：判断一张带符号图中是否存在能让总权重无限缩小的循环、任务依赖图中是否存在非法循环依赖、以及差分约束系统是否有解。差分约束系统把每个不等式拆成一条有向边，系统有解等价于图中不存在负环，用的就是上面这一模一样的模板。所以把这题吃透，等于顺手掌握了好几个完全不同领域里"是否存在坏循环"的统一判据。

最后分享一个我个人的调试习惯。遇到这类环检测题，我从来不在脑子里硬推松弛过程，而是先在纸上把环的边权乘积手算一遍，确定到底有没有套利，再用一个三节点的自造数据跑一遍代码，确认输出和手算结果一致。这个习惯帮我挡下了至少三次因为 eps 方向写反或者初始值选错导致的隐蔽错误。纸上推演两分钟，比在 OJ 上反复提交试错要省事得多。