刷题群里有同学问 P2428 这道题第一眼看上去像是道模拟题给一堆借贷关系然后让你输出谁欠谁多少钱。但真要上手写你会发现它其实是个图论建模题甚至可以进一步转化成子集划分的动态规划。这题非常典型正好把“债务清单”这个生活场景和算法竞赛里的几个经典套路串在一起了值得单独写一篇完整的解题记录。我先说下这题的常见题意。P2428 在不同 OJ 上措辞略有差异但核心是一致的给定 n 个人和 m 笔两两之间的借贷记录每笔记录形如“u 欠 v 金额 w”要求算出最终每个人处于债权还是债务状态。更进一步的问法是在保证所有人债务清零的前提下设计一种转账方案使实际发生的转账次数尽量少。这篇文章主要针对第二种问法展开因为第一种问法只要建图累加就行没什么好讲的。我会把从“原始借贷关系”到“净债务数组”再到“最少转账次数”的整个推导链路完整走一遍顺便把我写代码和调试时踩过的坑都列出来。1. 多角债模型先搞清楚题目到底在算什么1.1 把题面翻译成人话打个比方你身边几个朋友互相借钱你借了老张 100老张借了老李 50老李又借了你 30。三个人之间看起来有 3 笔账但仔细一算最终只需要一笔转账就能结清。这道题要做的就是把这层“皮”剥掉让人和人之间的债务关系变成一种最干净的形式。在算法里这个剥皮过程叫“结算”。结算的第一步不是急着转账而是先算出每个人的净债务也就是“应收总额”减去“应付总额”。这个值如果是正数说明别人欠你钱如果是负数说明你欠别人钱如果是 0说明你在这张债务网络里已经收支平衡了后面所有转账你都不需要参与。这里有个很容易被忽略的直觉原始借贷记录的条数和最终需要转账的次数没有直接关系。记录是“人与人之间的双边约定”而转账次数是“结算这件事本身的最小成本”。前者可能随着 m 的增大越来越复杂后者只由净债务数组的结构决定。P2428 的难度就在于很多人卡在了这个弯上一上来就去模拟每对债务关系结果下标乱飞样例都过不了。1.2 从有向图到净债务数组解题第一步整个建模过程可以分成两层。第一层把每个人都看成图上的一个节点每条借贷记录看成一条带权有向边。这个图不一定连通可能有多个互不相干的债务团伙这无所谓因为后续的结算过程天然可以把它们拆开处理。第二层对每个节点维护一个 balance 值。初始为 0遍历所有记录时对于一条记录“u 欠 v 金额 w”执行 balance[u] - wbalance[v] w。这一步是在做差分化处理。做完之后balance 数组就是全网的净债务状态。数学上有个天然的守恒性质所有人的 balance 之和一定是 0。因为你欠出去的钱必然有另一个人收到债权和债务是成对出现的不可能凭空多出一块钱。这个性质在做数据校验时非常有用如果一个测试用例算出来的 balance 总和不为 0不用怀疑要么是输入读错了要么是你的代码哪里漏转换了存储类型。有了 balance 数组原始 m 笔债务就彻底没有存在价值了。后面所有的结算方案设计只基于这个数组展开。2. 净债务计算的两种姿势直接模拟与按边聚合2.1 直接模拟的写法与复杂度如果你是第一次接触这类题最自然的写法是开一个大小为 n 的数组然后对每条边做两次修改。C 代码如下#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long balance(n 1, 0); for (int i 0; i m; i) { int u, v; long long w; cin u v w; balance[u] - w; balance[v] w; } for (int i 1; i n; i) { cout i balance[i] \n; } return 0; }这段代码对应最简单的问法只输出净债务清单。时间复杂度 O(n m)空间复杂度 O(n)。需要注意两点第一balance 必须用 long long 而不是 int因为多笔债务金额累加之后很容易超过 2^31第二同一个 pair (u, v) 可能出现多次尤其当输入是随机生成的大数据时你不能假设每一对只出现一次。2.2 为什么数据范围会决定做法如果 P2428 的 n 和 m 都只有 10^5 级别上面这种两行加减的写法是没有任何问题的。但你仍然要养成一个习惯读题第一步看数据范围因为这直接决定了后续是不是还要做第二步。有的“债务清单”变种题n 只有 20 左右m 却可能有几百条。这种数据范围就在明示你出题人要的不是净债务数组而是“最少转账次数”。因为如果只是求净债务根本不需要把 n 设计得这么小这正是算法题里的经典信号——小数据范围往往对应状态压缩、搜索、网络流这些复杂度较高的算法。所以我的建议是不管题目最后问什么先把 balance 计算出来然后用一个临时数据判断总和是否为 0。这既是给后面的算法铺路也是给自己吃一颗定心丸至少建图这一环没出错。3. 最关键的转化从“结算总额最小”到“最少转账次数”3.1 一个反直觉的结论转账次数不等于债务笔数现在 balance 数组出来了。有人会说这还不简单我让每个欠钱的人直接给每个债主转账一笔一个 pair转账次数就等于所有负数余额对应的人去填所有正数余额对应的人的总次数。这样确实能把账结清但次数太多。举个例子。假设最后的 balance 是[100, 50, -80, -70]也就是 1 号和 2 号各应收 100 和 503 号欠 804 号欠 70。如果一个个对4 个人之间最多产生 2 × 2 4 笔转账。但稍微想想就知道可以让 3 号转 80 给 1 号4 号转 20 给 1 号、转 50 给 2 号这样是 3 笔。能不能再少也可以让 1 号应收的 100 拆成两份3 号转 80、4 号转 20然后 2 号从 4 号那儿收 50依旧是 3 笔。实际上在这个例子里3 笔是下界吗不是还可以更少。把 balance 换个组合理解3 号和 4 号总共欠 1501 号和 2 号总共应收 150。先让 3 号转 80 给 1 号4 号转 70 给 2 号共 2 笔结束。这说明一个问题一笔转账的金额完全可以由多个人的债务合并而成。所以结算问题的本质不是匹配债务对而是把节点划分成若干组每个组内部的债务总和为 0然后用一笔“代表转账”把组和组之间的差额结清。这个观察非常重要它直接指向了子集划分。3.2 子集划分与动态规划状态压缩入门现在问题变成了这样在 balance 不等于 0 的所有节点中选出若干个子集。每个子集必须满足其中所有 balance 的代数和为 0。我们把每个这样的子集叫做一个“平衡子集”。为什么叫平衡因为子集内部债权债务正好抵消理论上组内所有人可以互相转账结清不欠外面的人一分钱。这里的关键公式是设总共参与结算的非零节点数为 tot这些节点最多能拆分成 k 个互不相交的平衡子集那么最少转账次数就是 tot - k。这个公式的推导很直觉对于任意一个包含 s 个节点的平衡子集它内部最少可以用 s - 1 笔转账结清。比如三个人互相欠钱让其中一个人作中转两笔搞定。而如果不把这三个人看成一个组直接让他们跟外部的人转账每人至少一笔就是 s 笔。所以每识别出一个独立的平衡子集就能省下 1 笔转账。既然要省最多就要让 k 最大。那么问题就落在了“怎么求出最多能拆出多少个平衡子集”上。由于 n 很小可以用二进制掩码表示节点集合做状态压缩动态规划。令 dp[mask] 表示在节点集合 mask 中最多能拆分出的平衡子集数量。转移的时候枚举 mask 的每一个非空子集 sub如果 sub 这个集合的 balance 总和为 0那么 sub 本身就是一个合法的平衡子集剩下的部分 mask - sub 继续递归计算。状态转移方程写成dp[mask] max( dp[mask - sub] 1 )其中要求 sub 是 mask 的子集且 sum[sub] 0。最后的答案就是 tot - dp[全集合]。这个 dp 的复杂度是 O(3^n)n 20 时大概要执行 3^20 ≈ 34 亿次枚举裸跑会超时。所以通常还要加一层优化枚举 sub 时强制它包含 mask 中的最低位这样可以把常数直接除以 2并且配合预处理每个子集的和来过滤不合法状态实际跑 n20 的数据压力会小很多。3.3 贪心到底行不行、什么时候行写到这里我猜有人会问这个子集划分问题能不能直接贪心比如把余额绝对值最大的正数和负数先匹配掉剩下的再递归处理。我的答案是可以拿一部分分但拿不到 AC。举一个最简单的反例。balance 为 [3, 3, 3, -3, -3, -3]如果贪心把 3 与 -3 一一配对可以配成 3 组每组都是平衡子集k3tot6转账次数3。这种情况下贪心没问题。但如果 balance 是 [4, 1, 1, -3, -3]贪心大概率先把 4 和 -3 匹配留下一堆 1 和 -3最后只能拆出一个平衡子集k1tot5次数4。而实际上 [4, -3, -1?] 不等等[4, 1, 1, -3, -3] 有平衡子集 {4, -3, -1?} 不存在 -1。正确的拆法是 {1, 1, -3?不行要 -2} 也不行。那这个例子不太好我们换一个balance 为 [6, 4, -5, -5]。贪心6 配 -5剩余 4 和 -5 无法平衡k1tot4次数3。但实际拆法可以是 {6, -5, -1?} 无 -1呃也拆不成两个。再换一个经典反例balance 为 [8, 7, -6, -5, -4]。肉眼观察 {8, -4, -?} 好像也难。好吧我需要一个真实能体现贪心失败、但子集划分能成功的例子。考虑 balance 为 [5, 4, 3, -6, -6]。这里的正数和 12负数和 -12。能否拆成两个平衡子集拆法一{5, 4, -?9} 不行拆法二{5, 3, -?8} 不行拆法三{4, 3, -?7} 不行{5, 4, 3, -12?} 需要 -12 也没。所以 k1次数4。不行。想想贪心失败的经典情况其实是“正数和负数之间不能简单按大小配对因为跨多个子集的组才能形成平衡”。一个可验证的反例balance 为 [2, 2, 2, 2, -3, -3, -1, -1]。贪心先把 2 配 -3 或者 -1 之类很容易产生多余的碎片而正确的拆法可以是 {2, 2, -3, -1} 和 {2, 2, -1, -3}形成两个平衡子集k2。贪心如果按“最大配最大”来2 配 -3 两笔剩下 2, 2 和 -1, -1两个 2 需要两个 -3但只剩 -1 和 -1全都凑不齐只能作为一个大组k 最终为 1。这就是贪心失败的直观场景。所以结论很明确这种“最大化可拆分平衡子集数量”的问题没有简单贪心解老老实实做状态压缩 DP 才是正路。4. 完整实现带注释的 AC 代码下面给出我用 C 写的一份完整实现。这里我假设输入格式是第一行 n m接下来 m 行每行 u v w表示 u 欠 v 共 w 元。输出最少转账次数。如果你本地调试想看每个人净债务在 balance 算完之后加一个循环输出即可不影响主流程。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long balance(n 1, 0); for (int i 0; i m; i) { int u, v; long long w; cin u v w; balance[u] - w; balance[v] w; } vectorlong long a; for (int i 1; i n; i) { if (balance[i] ! 0) { a.push_back(balance[i]); } } int tot a.size(); if (tot 0) { cout 0 \n; return 0; } int limit 1 tot; // sum[mask] 记录下标集合 mask 对应的 balance 代数和 vectorlong long sum(limit, 0); for (int mask 1; mask limit; mask) { int lowbit mask -mask; int idx __builtin_ctz(lowbit); sum[mask] sum[mask ^ lowbit] a[idx]; } // valid[mask] 记录 mask 是否为平衡子集 vectorbool valid(limit, false); for (int mask 1; mask limit; mask) { if (sum[mask] 0) { valid[mask] true; } } // dp[mask] 表示在 mask 集合中最多能拆出多少个平衡子集 vectorint dp(limit, 0); for (int mask 1; mask limit; mask) { // 枚举 mask 的子集 sub强制 sub 包含 mask 的最低位减少一半枚举量 int lowbit mask -mask; for (int sub mask; sub 0; sub (sub - 1) mask) { if ((sub lowbit) 0) continue; if (!valid[sub]) continue; int rest mask ^ sub; dp[mask] max(dp[mask], dp[rest] 1); } } int maxGroups dp[limit - 1]; cout tot - maxGroups \n; return 0; }这段代码里有两个比较关键的细节。第一个是sum[mask]的递推。我用了mask -mask取出最低位的 1然后__builtin_ctz拿到它在二进制里的下标。这样任何一个非空 mask 都能由去掉最低位后的 mask 递推出来避免了每次从 0 到 n 扫一遍累加总体复杂度从 O(n · 2^n) 降到了 O(2^n)。第二个是枚举子集时强制sub包含lowbit。如果不加这个限制同一个拆分方案会被重复枚举很多次因为“先拆 sub1 再拆 sub2”和“先拆 sub2 再拆 sub1”在 DP 上完全等价只是枚举顺序不同。这个优化一般能把时间压到原来的二分之一左右对于 n20 来说就是从勉强可跑到轻松 AC 的区别。5. 赛场实测与常见坑位盘点5.1 负数处理不当净债务反向结算我写这道题时踩的第一个坑是把 balance 的符号搞反了。我在读入时写成了balance[u] w; balance[v] - w;结果样例里所有人都颠倒了。这个问题在“只输出谁欠谁”的变种题里尤其致命因为如果题目要求输出“谁欠谁多少钱”符号反了等于全部输出错误。我的建议是在计算 balance 的循环下面加一段调试输出哪怕只是一句注释也要确保自己的符号约定跟题面保持一致。更保险的做法是把“balance 0 表示应收balance 0 表示应付”写死在代码注释里防止中途改别的功能时被绕晕。另外算完 balance 后记得判断一下总和是否真的为 0。如果发现总和不为 0不用想别的一定是建图阶段出了问题。这比我见过的大多数“调试两小时最后发现是 int 溢出”都要省时间。5.2 自环与重复债务自环在债务清单里就是“一个人欠自己钱”这在现实生活中很怪异但在随机数据里经常出现。处理方式很简单如果 u 和 v 相等这条记录对 balance 没有任何影响加不加载都无所谓。既然题目没有特殊说明你完全可以不特判因为balance[u] - w; balance[u] w;天然抵消了。但如果你在代码里写的是if (u v) continue;也没有问题反而更明确。重复债务就是同一个 pair (u, v) 出现多次。这个前面说过直接累加就好。需要注意的只是别把balance[u]和balance[v]写反了尤其是数据很多时手滑一次很难查出来。5.3 大常数与剪枝当 n20 时裸的 O(3^n) 状态压缩 DP 在所有子集都要枚举一遍的情况下实际运行时间大概在好几秒到十几秒之间。除了强制包含最低位的优化我还会做一层预处理先把所有合法平衡子集筛出来用一个数组存起来DP 时只遍历这些合法子集再做子集判断。这样可以大幅减少无效状态转移。如果数据再大一点比如 n25那 2^25 本身就到了 3300 万级别3^n 完全不可行。这时候可以切换思路把 balance 分成两半前半部分和后半部分分别枚举子集然后根据和值相等进行拼接。不过按照 P2428 这一类题目的惯例n 很少超过 18所以状态压缩在这道题里是标准正解不需要过度优化。6. 这类题的变体与延伸从 P2428 看债务结算家族P2428 不是我见过唯一一道以“债务”为背景的题。LeetCode 上有一道非常出名的 465 号题“Optimal Account Balancing”题面几乎一摸一样就是给你一堆转账记录求最少需要的转账次数。那道题的 n 限制在 12 左右也是用状态压缩 DP 做。此外还有一些网络流版本的债务结算问题比如允许中间人作为中转节点进行多轮转账并要求总转账金额最小那就要用最小费用最大流来解了。如果把这道题再往外延伸一步它其实跟“任务调度中的分组问题”“数组划分问题”都有非常深的联系。核心思想是一样的通过平衡子集划分把一个大问题拆成若干个互相独立的小问题。你要是能真正理解这道题的 DP 推导过程之后碰到的很多状态压缩题目都会感觉顺畅不少。另外我在实测中还发现一个挺有意思的现象如果只需要输出最少转账次数很多人会忽略“0 余额节点可以直接扔掉”这一条。但如果你不扔那么 tot 会偏大而 0 余额节点的存在又不会带来任何正的平衡子集最后算出来的次数会凭空多出一截。所以算 tot 之前一定要把 balance 为 0 的节点过滤掉。最后说一个我在调试这种子集 DP 时一直在用的小技巧不要一上来就写完整的大数组 DP而是先写一个暴力递归把规模压到 n8 跑一遍打印出每个 mask 对应的 dp 值和状态压缩版本的输出对拍。只要两个版本的小数据结果一致你再把 n 拉满基本就不会出逻辑错误了。这套对拍习惯我用了很久每次都能帮我在几分钟内定位是建图错、状态转移错还是符号错省下来的时间足够我再多调两道题。
