题解：AT_abc461_g [ABC461G] Graph Problem 2026

· · 题解

赛时快速切掉，并且第一次进 100 名。

赛时首先看到范围只有 5\times 10^4，怕不是网络流？

感觉贪心的选，他每一个 W_i \in \{0,1013,2026\} 会是最优的。

后面才知道这个东西叫做半整数线性规划。他是一个关于把权值划成 \{0,\dfrac{W}{2},W\} 的模型，而且那个结论能证明这样选择会是最优的（但我也不会）。

不妨将每一个点 W_i 拆成两个点 l_i,r_i，l_i,r_i \in \{0,1013\}。意义上 W_i = l_i + r_i。这样 W_i 的三个权选择就转化为 l_i,r_i 的选与不选。

然后由于 (u,v) 一条边约束着 W_u + W_v \le 2026，那么说明存在某种关系，就是对于约束的边 (u,v) 的 l_u,l_v,r_u,r_v 的选与不选是相互依赖的。

它的依赖关系是？

看到这样的约束条件想到去构造一个二分图，对于每一个 $(u,v)$，连接二分图上 $l_u \to r_v$ 和 $l_v \to r_u$。那么 $l_u,r_u,l_v,r_v$ 四个点的**最大独立集**就是 $2$，解决了上面的约束条件。 那么对于那些没有连接的点，他在最大独立集里就会贡献出 $2 \times 1013 = 2026$，相对应的实际意义就是 $W_i = 2026$。 所以结论就是，答案为最大独立集个数 $\times 1013$。二分图上最大独立集求个匹配就行。 感觉这一类题比较靠感觉，需要合理利用网络流建图来约束一些约束关系。例如这题就是找到相互**对立**关系，然后连边，那么出来的就是最大独立集。 [code](https://atcoder.jp/contests/abc461/submissions/76474346)。