ABC461G

ABC461G - Graph Problem 2026

$N$ 点 $M$ 边简单无向图，在点权 $w$ 满足如下条件时，求 $\sum{w_*}$ 的最大值。

• 对每个点 $i$，$w_i \in \lbrace 0, 1, 2 \rbrace$。
• 对每个边 $(u,v)$，$w_{u}+w_{v} \in \lbrace 0, 1, 2 \rbrace$。

拆点，令 $w_{i}=w_{i_{0}}+w_{i_{1}}$，并钦定 $w_{i_{0}},w_{i_{1}} \in \lbrace 0, 1 \rbrace$，问题将三个权选择化为每个点的选与不选。希望所选点最多。

考虑边的约束 $w_{u_{0}}+w_{u_{1}}+w_{v_{0}}+w_{v_{1}} \in \lbrace 0, 1, 2 \rbrace$，拆分：

• $2,0 = 1,0 + 1,0$，选 $u_0, u_1$，不选 $v$。
• $1,1 = 1,0 + 0,1$，选同侧的 $u_0, v_0$ 或 $u_1, v_1$。
• $0,2 = 0,1 + 0,1$，选 $v_0, v_1$，不选 $u$。

在新图中连交叉边 $(u_0, v_1)$ 和 $(u_1, v_0)$ 得到二分图。原问题等价于求二分图的 MIS。