[SHOI2011]银行家 题解

link
好的考场上打的伪作法，想必很容易想到：从 \(1\) 到 \(n\) 用并查集维护某两个元素是否在一个人中出现过，若出现，则连接。那么一个联通块就有一个统一的贡献，直接分配即可。
不妨探究这样为什么是错的。发现如果 \(x\) 和 \(y\) 先连接，他们加起来的 money 是 \(0\)。但是之后你又将 \(y\) 连 \(z\)，\(z\) 的 money 是一个很大的数，那么 \(x\) 便可以用 \(z\) 的 money，这样显然是错误的。
之后发现确实 不好贪心地分配，那就 网络流 啊！！！！然后往网络流的方向想，发现是板子。