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\),那么做法是:

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

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

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

AC code

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

————————

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\),那么做法是:

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

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

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

AC code

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