我前几天整理刷题记录翻到一道 P2428 债务清单第一眼以为这种题就是给账本做数据清洗但仔细手推了两组例子之后发现它其实是包装得很好的图论压缩题。很多人拿到题目会直接去模拟“A 欠 BB 欠 C于是 A 欠 C”的合并过程结果要么死循环要么遗漏了可以合并的长路径。这篇文章我就把这道题从建图、分层、传递闭包到代码实现的完整思路捋一遍适合正在练图论建模、准备比赛或者单纯对债务抵消与关系压缩感兴趣的朋友。P2428 这道题的核心是给出一群人和一堆债务关系债务可以在中间人之间传递抵消最终要输出一张尽可能精简的债务清单。听起来像财务系统里的“多边净额结算”但落到算法层面它其实考察的是有向图中的路径替代、连通性判定以及按权值分层的技巧。接下来我按实际做题时的思考顺序来写先拆题再讲为什么这样建模最后给出能直接跑的代码和踩坑记录。1. 问题拆解债务清单到底在算什么1.1 从题目描述到图论语言先把题目翻译成图。每个人是图里的一个点如果 A 欠 B 十块钱就画一条从 A 指向 B 的有向边边权是 10。这样所有债务关系就构成一张有向带权图。所谓“合并债务”就是当我们发现 A 指向 B、B 指向 C并且两条边的金额相同时可以删掉这两条原始边再补一条 A 指向 C 的相同金额边。这一步非常关键因为很多相似题是允许任意金额做差值的比如 A 欠 B 10 元、B 欠 C 7 元合并成 A 欠 C 3 元之后还要考虑 B 和 C 之间谁欠谁。P2428 的标准设定里只有金额完全一致才能直接传递合并所以题目天然退化成“相同金额边之间的路径压缩”。为什么要强调金额一致因为一旦金额不同问题就从“判断可达性”升级成了“求路径上的最小边权”甚至“拆分数值”复杂度完全不同。P2428 故意用相同金额这个限制把最难的数值运算拿掉剩下的核心就是纯粹的结构判断一条边能不能被“绕过去”。举个例子A 欠 B 5 元B 欠 C 5 元C 欠 D 5 元。如果只看有没有可合并的操作A 到 C 可以先合并得到 A 欠 C 5 元然后 C 欠 D 5 元继续合并得到 A 欠 D 5 元。这个过程相当于在图里找到一条从 A 到 D 的长度为 3 的路径并把它压成一条直达边。所以最终留下来的一定是那些“不经过其他人就无法替代”的必要债。1.2 三个关键难点第一个难点是不要陷入模拟循环。有人拿到题就开始 BFS 模拟合并每合并一次就删边加边然后继续找。问题是合并顺序会严重影响效率而且同一个环路上可能反复触发合并代码写起来很容易乱。第二个难点是处理“长路径替代”。一条边不仅可能被两条边替代还可能被三条、四条甚至更多条边组成的路径替代。模拟的时候容易只检查相邻两条边漏掉多跳路径最后给出的清单不是最优的。第三个难点是浮点数与精度。债务金额虽然听起来自然带小数点但绝大多数题目为了避坑都会给整数金额。如果题目确实给小数那比较两个金额是否相等时不能用得用 eps。就算给整数也要小心大整数相加溢出边权很大时中间结果可能超过 int 范围。这三个难点决定了我们的解法方向不能单纯模拟必须先做图论建模再想办法在一次预处理里判断所有可替代边最后统一输出。2. 建模思路与算法选型2.1 按金额分层把复杂债务拆成互不干扰的子问题既然只有相同金额的边才能合并那我们可以把原图按照边权拆成若干张子图。每张子图里的边权都相同子图之间没有任何交叉影响。这个“按权值分层”的思路在动态规划里叫分组处理在图论里其实也很常用尤其是遇到权值参与转移条件的时候。分层之后原问题变成对每一张子图把其中可以通过两条或更多条边替代的冗余边找出来删掉。不同金额的边永远不会互相协助所以分层不会丢失正确答案。举个例子A 欠 B 5 元B 欠 C 5 元同时 A 欠 C 3 元。5 元层里有 A 到 B、B 到 C 两条边3 元层里有 A 到 C 一条边。A 到 B 到 C 合并成 A 欠 C 5 元和原本 A 欠 C 3 元是两条独立的债务不能因为你欠我 3 元、我欠你 5 元就做减法抵消。这个例子说明分层时一定要把不同金额完全隔离否则就会错误合并。实现上可以用一个哈希表键是金额值是该金额覆盖的点集和边集。因为点数通常不大我习惯用一个结构体存储每个金额对应的邻接矩阵或边列表。分层之后的数据规模会小很多很多子图其实只有一两条边处理起来非常快。2.2 传递闭包与冗余边判断子图建好之后需要判断每条边是不是冗余的。冗余的定义是删除它之后起点仍然可以通过其他路径到达终点。这个定义和图论里的“传递闭包”高度重合。如果用邻接矩阵存子图先对每个金额层跑一次 Floyd-Warshall 求可达矩阵。如果点 u 能到达点 v矩阵reach[u][v]就是 true。然后遍历该层所有原始边(u, v)只要存在一个中间点 k使得reach[u][k]和reach[k][v]同时为 true就说明这条边可以被一条经过 k 的路径替代应该删掉。这个条件看着简单但很多人会写错成“只要reach[u][v]为 true 就删边”。这是不对的因为原边本身就贡献了reach[u][v] true。如果只有一条直达边没有中间点那它是唯一债不能删。所以要额外枚举中间点 k保证是长度至少为 2 的路径。再强调一个细节如果 u 到 v 有三条边其中两条是同样的金额一条是不同金额那条不同金额边不能参与替代。所以在每一层的可达矩阵里只考虑本层边这正好呼应了 2.1 的分层设计。2.3 复杂度分析与数据范围取舍假设总人数为 n总债务条数为 m不同金额层数为 k。每个金额层内部跑 Floyd-Warshall 的复杂度是 O(n^3)多个层加起来是 O(k * n^3)。如果 n 是 100k 是 100那么 100 * 100^3 等于一亿次在 C 里勉强能跑在 Python 里就比较吃力。因此我写代码前会先看数据范围。如果 n 比较小比如不超过 100那就直接对每一层做完整的 Floyd-Warshall思路最清晰。如果 n 到了 1000Floyd-Warshall 就彻底爆炸了这时候应该换成 BFS 或 DFS 做每点可达性检查对每个点跑一次图遍历复杂度 O(n * (n m))只要图稀疏反而比 Floyd 快得多。我做题时的选型优先级是这样的数据规模推荐算法理由n 100按金额分层 Floyd-Warshall实现简单不用考虑递归栈n 500 且图较稀疏对每个金额层做 BFS/DFS 可达性复杂度由边数主导金额层特别多先压缩点集只处理实际出现的点减少无效计算还有一种情况是点数少但边数很多比如 m 接近 n 的平方。这时候邻接矩阵反而比邻接表好用Floyd-Warshall 的三重循环在局部性上比 BFS 更好常数更小。所以没有绝对最优算法还是要看具体数据长什么样。3. 核心代码实现与细节处理3.1 C 实现主体我的实现思路分四步读入并分层每层建邻接矩阵跑可达性最后收集所有不可被替代的边。因为题目数据一般不大我直接用vectorvectorint存邻接矩阵避免动态开二维数组带来的麻烦。下面是主体代码我把注释写详细一点方便直接对着抄#include bits/stdc.h using namespace std; const int MAXN 505; int n, m; // 用来记录最终答案的边 struct Edge { int u, v, w; bool operator (const Edge other) const { if (u ! other.u) return u other.u; if (v ! other.v) return v other.v; return w other.w; } }; int main() { scanf(%d%d, n, m); // g[w][u][v] true 表示金额为 w 的边中u 到 v 存在直接边 // 因为金额可能是负数这里可以用 map 统一管理 mapint, vectorvectorint g; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); if (g.find(w) g.end()) { g[w] vectorvectorint(n 1, vectorint(n 1, 0)); } g[w][u][v] 1; } vectorEdge ans; for (auto it : g) { int w it.first; auto mat it.second; // 邻接矩阵 // 先把原图的所有边备份出来 vectorEdge edges; for (int i 1; i n; i) { for (int j 1; j n; j) { if (mat[i][j]) { edges.push_back({i, j, w}); } } } // Floyd-Warshall 求传递闭包 vectorvectorint reach mat; for (int k 1; k n; k) { for (int i 1; i n; i) { if (!reach[i][k]) continue; for (int j 1; j n; j) { if (reach[k][j]) { reach[i][j] 1; } } } } // 判断每条原边是否冗余 for (auto e : edges) { bool canReplace false; for (int k 1; k n; k) { if (k e.u || k e.v) continue; if (reach[e.u][k] reach[k][e.v]) { canReplace true; break; } } if (!canReplace) { ans.push_back(e); } } } // 按起点、终点、金额排序输出 sort(ans.begin(), ans.end()); printf(%d\n, (int)ans.size()); for (auto e : ans) { printf(%d %d %d\n, e.u, e.v, e.w); } return 0; }这段代码有一个小问题原边如果有多条相同金额的重复边mat[u][v] 1只保留了一条这是合理的因为两张完全相同的借据合并成一张金额不变对最终清单没有影响。如果题目要求保留所有重复边那再单独加一个计数数组但大部分 OJ 不会这么刁钻。3.2 避免浮点误差用整数处理金额题目里的金额如果是整数直接存 int 就好。但我在实际练习时遇到过金额给两位小数的版本比如 5.23 元。这时候我强烈建议把所有金额先扩大 100 倍转成整数再进入哈希表分层。为什么要这么做因为浮点数0.1 0.2不等于0.3的问题在比较两个金额是否相等时会直接爆雷。你以为 A 欠 B 的 0.3 和 B 欠 C 的 0.3 是同一个金额但在 double 里存下来之后两个数的二进制表示可能并不一致。转成整数之后所有比较都变成精确的整数比较完全规避浮点误差。转成整数之后还有一层好处排序输出的时候只要把整数金额再转回两位小数即可。转回去的时候要小心四舍五入比如整数是 1005金额就是 10.05 元整数是 1000金额就是 10.00 元。如果原题用空格分隔整数和小数那就更简单直接输出整数部分和小数部分。我在代码里没有加入金额转换是为了让核心逻辑更纯粹。如果你做的是带小数版本只需要在读入时int scaled_w (int)round(w * 100);存进 map最后输出时再printf(%d.%02d, scaled_w / 100, scaled_w % 100);即可。3.3 输出的坑排序与去重输出是整个题目里最容易被扣分的地方。很多题目的 Special Judge 会忽略顺序但如果不排序你本地的样例可能对交上去却因为格式问题 WA。所以稳妥起见我把所有要输出的边先存起来按起点、终点、金额三级排序再逐行输出。排序还有一个额外好处去重变得非常直观。如果你在某层里检测到一条边(u, v, w)被多条真实借据对应去掉重复借据后只剩一条。排序后相邻元素相同直接跳过即可。不过要注意这个去重逻辑必须在进入答案集合前完成不要在输出时才跳过否则会影响后面边的判断。另一个坑是自环。如果输入里出现了u u w也就是自己欠自己钱这种边在数学上是无意义的应该直接忽略因为债务关系没法从一个人转移到他自己头上。我在这份代码里没有显式过滤自环是因为邻接矩阵如果mat[u][u] 1Floyd 算法会把很多点连通性搞乱。所以读入的时候看到u v就continue掉是最安全的做法。4. 测试验证与样例推演4.1 手推一个小例子我拿一个特别简单的样例来完整走一遍流程。三个人 A、B、C输入如下3 3 1 2 5 2 3 5 1 3 5金额都是 5所以只有一层图。边有 1-2、2-3、1-3。矩阵里reach[1][2]和reach[2][3]都是 true因此reach[1][3]也是 true。遍历原边时1-2 这条边找中间点 kk3 时reach[1][3]为 true但reach[3][2]为 falsek2 时 k 等于终点所以没有合法中间点不能删。2-3 类似不能删。1-3 这条边k2 时reach[1][2]为 truereach[2][3]为 true所以可以删。最终输出两条边1-2 金额 52-3 金额 5。这个结果符合直觉因为 1 欠 2、2 欠 31 对 3 的债只是中间传导出来的不是真实原始债。再看一个更绕的例子加入环之后结果会不一样。四个人 A、B、C、D边是1 2 5 2 1 5 2 3 5 3 4 5 1 4 5这里 2-1 和 1-2 形成了一个环但环并没有给 1 到 4 提供新路径。逐条检查后1-4 可以通过 1-2-3-4 替代所以删除 1-4。但 2-3 没有替代路径因为虽然 2 可以走到 1但 1 走回 2 后还是停在原处没法不经过 2-3 到达 3。这个例子提醒我们可达性是单向的不能看到环就以为所有边都能删。4.2 随机数据对拍刷题的时候最怕思路对了但代码有隐藏 bug。我的习惯是写一个brute.cpp做暴力模拟再写一个solve.cpp放高效算法然后用脚本生成随机小数据不断对拍。暴力模拟的思路很简单每次扫描所有边如果找到两条相邻边u-v和v-w金额相等就删掉它们加入u-w。重复这个过程直到没有可合并的边。对小规模数据这个过程一定终止因为每合并一次边数减少一条。对拍脚本我一般用 Python 写循环 10000 次每次随机生成 n 在 1 到 6 之间的图和 m 在 0 到 15 之间的边边权从 1 到 3 随机。跑完对比两个程序的输出边集合是否完全一致。一旦不一致就把那组数据打出来定位。这里有个经验暴力模拟的合并顺序会影响最终边数所以对拍时不能只看边数还要看输出的每条边是否都合法以及是不是真的无法继续合并。如果两个程序输出的边数一样但是边集合不同可能是全局最优下存在多种等价方案这不一定是 bug需要人工判断合法性。更好的办法是拿暴力模拟得到的图再跑一遍“是否存在可合并相邻边”检查如果不存在说明它也是一个合法终态。4.3 边界情况我最开始把边界情况想得太简单结果交上去吃了几次 WA。列几个必须测的点只有一条边。此时没有任何中间点输出原边。两个点之间有多条不同金额的边。比如1 2 5和1 2 10两个金额层互不干扰都要输出不能删除任意一条。一个大环上所有边金额相同。比如1-2, 2-3, 3-1每条边都没有长度大于等于 2 的替代路径所以三条边全部保留。一个完全图所有边金额相同。此时每一条边都能找到一条长度为 2 的替代路径理论上最终一条边都不剩但这是不可能的因为如果删掉所有边图就没有方向性了。这里需要想清楚为什么完全图不能全删完全图的例子很有意思。假设有 4 个点每两个点之间都有边包括双向边。那么 1-2 可以通过 1-3-2 替代可以删3-2 也可以通过 3-4-2 替代也可以删。但如果你按这个顺序把所有边都删掉最后图里没有边那么这些点的原始债权债务关系全丢了。问题出在哪里问题出在我们一次性用“是否存在替代路径”删边时没有考虑这条替代路径可能也依赖那些我们即将删除的边。如果允许同时删除所有冗余边最终集合不一定是合法的。这就是我前面提到的最小等价图问题的难点。P2428 在这种小数据下通常可以用不断迭代合并来保证合法性每次只删除一条或者一组不影响其他边判断的边删除后重新计算可达性直到稳定。但在很多题解里大家会直接用“一次 Floyd 后判断是否存在长度大于等于 2 的路径”来删边这是因为题目数据或 Special Judge 做了特殊限制。我个人的建议是如果时间允许写一个迭代版本更稳妥每轮找出所有可删边真正删掉后再跑 Floyd如果这轮没有可删边就结束。这样边数上限只会更优不会更差。5. 常见问题与避坑清单5.1 超时与优化初学者最容易犯的错是对整个大图跑 Floyd而不是分层跑。如果不同金额的边混在一起Floyd 会把本来不连通的点连通导致错误删除。而且整个图跑三重循环复杂度是 O(n^3)多测几组就超时。正确做法是分层。但分层也要稍微注意常数我习惯先遍历一次原边把每个金额涉及的点单独存下来一个列表然后只对这些点开一个压缩后的邻接矩阵。比如金额 5 只涉及 A、B、C 三个人那就把这三人重新编号成 1、2、3矩阵大小 3x3而不是 500x500。这个“点压缩”技巧在金额层很多的时候能省下大量时间而且不会改变结果。另一个优化是剪枝。Floyd 内层循环里如果reach[i][k]已经是 false就跳过。这里用continue比用if包住整个内层循环更清晰。代码可读性和性能都能兼顾。5.2 重复边、反向边、自环重复边在数学上等价于一条边但程序里如果不去重edges里会多出很多一模一样的边最后答案数量和判断都会出问题。我处理的方法是在读入时直接对每个金额层建邻接矩阵重复边自然被矩阵覆盖。反向边是另一种情况比如1-2 5和2-1 5。这两条边不是重复边它们构成一个双向债。判断时要分别判断1-2 能不能通过 1-k-2 替代2-1 同理。在环里如果只有这两条边都不能删因为它们互为依赖删掉任何一条都会破坏另一条的可达路径。自环我前面提过直接忽略。这里补充一个坑有些题目允许自环并把它当成一种“一个人欠自己钱”的输入噪声。如果你不忽略Floyd 的reach[i][i]会变成 true这在某些写法下会导致判断冗余边时出现假阳性比如 k 取到 u 本身时如果reach[u][u]为 true可能错误地认为有一条长度为 0 的路径可以替代。所以我在枚举中间点时专门判了k e.u || k e.v时跳过。5.3 计数与类型溢出如果边权很大比如达到 10^9虽然比较时只需要整数相等但在某些扩展版本里你可能需要把两条路径上的金额做和。一旦求和不小心用了 int10^9 10^9 就爆了。建议所有涉及金额的变量统一用long long尤其是做题时看到金额范围没有明确给小时。输出边数也需要用int或long long但边数最多是 m所以 int 一般够用。真正容易爆的是 map 的 key 如果直接放金额而金额是 long long那写maplong long, ...就行千万别把金额强转成 int。5.4 审题陷阱合并是否允许跨金额这是最容易踩的坑没有之一。有些题目说 A 欠 B 10 元B 欠 C 7 元可以合并成 A 欠 C 3 元同时 B 和 C 之间的债务清零。这种题其实是在做“净额结算”跟 P2428 的“相同金额传递”完全是两种模型。我一开始以为 P2428 也是净额结算还写了一个维护每个点净债数的代码样例直接过了但提交后 WA 到怀疑人生。后来仔细读题才发现它要求“如果 A 欠 B 的金额等于 B 欠 C 的金额那么 A 可以直接欠 C 同样金额”。也就是说金额不能拆不能做差值。如果你读题时发现描述里有“金额相同”这个限定那就按本文的解法来如果描述里没有这个限定而是允许任意金额合并那你要先对每个点计算净债务再重新构图那个问题反而比 P2428 更简单。建议拿到题第一件事就是看金额约束不要凭样例猜题意。6. 从算法回到工程这个模型还能用在哪P2428 的债务清单模型不只是 OJ 上的练习题它在真实业务里有个很接近的场景叫“多边净额结算”常见于企业间应收账款清算、银行间同业拆借、平台商家账期结算。如果把每家公司看成一个点应付款看成有向边那系统要做的就是把三角债甚至多角债压成最少的真实依赖关系。这个模型还可以类比到依赖关系压缩。比如软件工程里模块 A 依赖 BB 依赖 C同时 A 又直接依赖 C这种直接依赖就是冗余的可以删掉让构建图的边数更少。传递闭包判断在这里的应用几乎和 P2428 一模一样只不过点变成了模块边变成了依赖方向。甚至人际关系里的“介绍人”也能套这个模型A 通过 B 认识 C如果 A 和 C 已经直接认识那 B 作为介绍人的关系就可以弱化。这种“路径冗余检测”本质上是同一张图。所以不要小看这一道题它把图论里最基础的可达性概念换了一个生活化的皮。只要掌握“按约束分层 传递闭包判冗余”这套组合拳以后碰到类似的关系压缩问题都能很快上手。最后分享一个我实际写代码时的小技巧先用暴力模拟通过小数据再用高效算法通过大数据两个代码都保留。暴力版虽然慢但在对拍时可以当标准答案。写完高效版以后不要急着交随手生成几组随机小数据跑一跑很多隐藏 bug 会在对拍时现出原形。这个习惯帮我避开了大量因为题意理解偏差、边界处理不当导致的 WA。