考虑如下抽象而来的问题：
你有若干物品，每个物品都有两种属性。现在你想把他们分成若干组，使得每组内物品至少某种属性都相同，使得 \(\sum_i S_i^2\) 组大小平方和最大。
利用费用流解决是 easy 的，但实际上有非常独特的最大权闭合子图做法。
先给出建图方案：不妨记属性为 \(a_i,b_i\) ，考虑把它们用两个桶记录下来 \(A_v,B_v\) ，源点向 \(i\) 号节点连容量为 \(A_{a_i}\) 的边，\(i\) 号节点向汇点连容量为 \(B_{b_i}\) 的边，同时，对于两种属性，相同的两个点 \((i,j)\) 连容量为 \(1\) 的双向边（完全相同连两条）。
相对自然地，我们可以将超理想状态—— \(\sum_i A_i^2+\sum_i B_i^2\) 设为初态，同时连好上述方案的前半部分。然而事与愿违，我们必须决定一个点用哪个属性。之前我们解决大部分非线性贡献/代价的问题时更多地关注到了网络流的贪心本质，然而在这里我们却依赖于一个非常优美的模型：团。首先它在任何一个状态时都表现地很好——点分成两部分时两边之间的边数是 \(|S|(n-|S|)\) ，即使是用网络流的视角来观察它也很优美，因为在只保留一边的贡献 \(\sum_{i\in S} A_{a_i}\) 或 \(\sum_{i\in S} B_{b_i}\) 时，再减去两边之间的边数就是答案。由此可见，这种拓扑模型完美地契合了我们需要的代数式。
标签：容量,记录,sum,网络,物品,边数,独特,属性 From： https://www.cnblogs.com/gooder-tmi/p/17045145.htmlLife is short...