问题

最近有人问我如何计算一群一起旅行并遇到一个有趣问题的人的欠款：鉴于您知道每个人的欠款额，合并人与人之间债务的一般算法是什么？这样只需要最少的付款次数？以此为例：

• 迈克欠约翰100
• 约翰欠瑞秋200
• 迈克欠瑞秋400

我们可以通过重新安排债务来免除Mike和John之间的付款，如下所示：

• 迈克欠约翰0
• 约翰欠瑞秋100
• 迈克欠瑞秋500

因为它很容易，所以我手动进行数学运算，但是那时我的程序员却想找出一种通用算法来为任意大的组运算。在我看来，这似乎是一种图形算法，因此我将其重新表示为图形：

以图形形式查看

• 顶点是组中的人
• 边缘被定向并通过所欠的量加权。例如，从Mike到Rachel的重量为500的边缘意味着Mike欠Rachel 500。
• 约束：每个节点的权重净和必须保持不变。
• 目标是找到具有仍可满足约束的最小边数的图。