NFLS2022 CSP 模拟赛 21 C

管理员

Link

题解

神仙调整题。

无解就是两点一边,神奇的是 std 并没有写无解情况(

设点 (u) 的权值 (sum_u)(u) 相邻边的边权和 (bmod3) 的结果。

考虑二分图怎么做,拉出整张图的 dfs 树,并给树边赋权使得让 (sum_u)(u) 的深度 (bmod 2) 的结果相同,这样只可能有根节点不合法,但是我们发现还有 (2) 的点权没有用到,所以我们可以任选根节点相邻的两条树边把它们的权值均 (+1),这样两个儿子的权值为 (2),根节点的权值为 (0),前提是要以度数大于 (1) 的点作为根。

假如不是二分图,假如我们令 (sum_u=c_u),那么同样能只让根节点不符合条件,但上面的调整法已经不能满足于此。。。

显然 (3) 种点权都用到了,改变根节点之外的点权很容易寄,所以我们只能改变根节点的点权。

只改变根节点的点权其实是能做的,但需要利用奇环,比如,五元环的所有点权值都是 (0),现要将其中一个点权值变成 (1),那么做法是:

[[0,0,0,0,0]rightarrow[0,0,0,2,2]rightarrow[2,0,0,2,1]rightarrow[2,2,2,2,1]rightarrow[0,0,2,2,1]rightarrow[0,0,0,0,1] ]

其它长度为奇数的环同理,做法基本相同。

这样,我们就可以通过若干次调整来只让根节点的权值发生改变,前提是根节点必须处在一个奇环内,所以先要跑一遍二分图染色找到任意一个奇环。

时间复杂度:(O(n+m))

AC code

http://www.nfls.com.cn:10611/submission/226240