A – Elections
直接做不太好做，很懵逼。可以考虑枚举 CCP 得到的票数，然后再从各大党派中各抢一张票。如果不够抢就直接抢最小的票。这样取 min 即可。
直接做不太好做，很懵逼。可以考虑枚举 CCP 得到的票数，然后再从各大党派中各抢一张票。如果不够抢就直接抢最小的票。这样取 min 即可。
比赛的 GG 不以自己的意志为转移。
kal0rona
做一个容斥即可，答案等于：
\[ f_0 – f_1 + f_2 – f_3 \]
其中 \(f_i\) 代表环上至少有 \(i\) 对矛盾。计算方式如下：
大概可以想到二分出时间，然后把所有的点往上跳，再把能跨子树分配的点进行分配。思路差不多就是这样，还是很自然的一个思路。
但是有一些细节值得注意：跨子树分配和当前子树覆盖的优先级需要处理好。如果这个不处理好只能拿到洛谷上 80% 的数据。这个地方我改了很久，最后发现需要把跨子树分配作为第一枚举，然后再在枚举之间二次枚举子树覆盖需求（放在堆里，贪心配对即可）。
正好在《组合数学》上看过一个结论：反图形成的连通块的点在原图一定处处连通。证明很简单：考虑点对\((u, v)\)，如果点对之间在反图中不连通显然是在原图联通的；如果在反图中连通，有一个不在当前点集的点使得他们连通。所以，我们只需要构建反图，根据「不与本点相连的点都在本连通块内」进行 BFS 即可。
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。