AGC006F Balckout

sry_ · 2021-03-01 20:58:59 · 题解

给定一个 n\cdot n 的网格图，有些格子为黑。如果 (x,y),(y,z) 均为黑，则 (z,x) 也为黑，求最终黑色点的个数。

1\leq n,m\leq 10^5

该题解主要证明其他博客上很显然的结论。。。

很容易想到若存在 (x,y) 则建图 x\rightarrow y 。

考虑一个弱联通图的情况，而整图的情况可以看成弱联通图的乘积。

由于操作可以分为 y ，指向 y 的与被 y 指的，有三种情况，考虑对该图三染色，即若有 x\rightarrow y 那么 col_y=col_x+1\bmod 3 ，注意图是若联通。

那么会发生一下三种情况之一。

先考虑情况 2 和 3 ，最后考虑情况 1 。

情况二

结论：黑色点的个数等于原先边的个数。

若图只能用 1/2 种颜色那么肯定不会存在 x\rightarrow y,y\rightarrow z 的边，那么不会产生新的边，即不会有新的黑点产生。

情况三

结论：我们设 c_{0/1/2} 分别表示 col=0/1/2 的个数，那么黑点个数为 c_0c_1+c_1c_2+c_2c_0 ，即集合按照 0/1/2 顺序连边。

如果图能被三染色那么肯定存在一条链 u\rightarrow v\rightarrow w 满足 col_u=0,col_v=1,col_w=2 。

显然这三个点肯定满足上述结论。

考虑归纳构造，若当前图 G 满足构造，新加入一条边 u\rightarrow p 。（由于 u,v,w 等价故我们仅用考虑 u 的情况）

定义 \{0/1/2\} 表示 col=0/1/2 点的集合。

由于 \{2\}\rightarrow u,u\rightarrow p ，那么 p\rightarrow\{2\} 。

由于 p\rightarrow \{2\},\{2\}\rightarrow \{0\} ，那么 \{0\}\rightarrow p 。

可以发现无法存在其余边的出现，得证。

如果 p\rightarrow u 类似，这里不在阐述。

情况一

结论：黑点个数为所在弱联通块点的个数的平方。

先去考虑一个子问题，由于三染色过程形成的是一个 dfs 树，而若存在矛盾仅能为返祖边，那么我们肯定能将其若联通块进行三染色并且会附赠一些矛盾的边。

若先不考虑矛盾的边那么依据情况三我们已经得到一个 \{0\}\rightarrow \{1\},\{1\}\rightarrow \{2\},\{2\}\rightarrow \{0\} 的边集。

解决当前问题的小结论

结论：若在一个三染色图上加入一个矛盾边那么肯定能让一个集合 \{x\},x\in\{0,1,2\} 满足 \{x\}\rightarrow \{x\} 。

证明这个也很简单，我们继续沿用情况三的 u,v,w ，证明也和情况三的类似。

若存在 u_1\rightarrow u_2 ，根据 u_2\rightarrow \{1\} 可得 \{1\}\rightarrow u_1 ，又由于 u_1\rightarrow \{1\} ，那么 \{1\}\rightarrow \{1\} 。
若存在 u\rightarrow w ，由于 w\rightarrow u 可得 u\rightarrow u 。可以归纳到上述证明。

得证。

继续考虑情况 1 的证明，根据当前的小结论可以得到该图存在一个 \{x\}\rightarrow \{x\} 的边，不妨将其设为 \{0\}\rightarrow \{0\} 。

由于 \{0\}\rightarrow\{0\},\{0\}\rightarrow \{1\} 可得 \{1\}\rightarrow \{0\} 。

由于 \{1\}\rightarrow \{0\},\{0\}\rightarrow \{1\} 可得 \{1\}\rightarrow \{1\} 。

由于 \{1\}\rightarrow \{1\},\{1\}\rightarrow \{2\} 可得 \{2\}\rightarrow \{1\} 。

同理可得 \{1\}\rightarrow \{2\},\{2\}\rightarrow \{2\} 。

由于任意两点均可以直接到达，图为完全图，那么黑点个数显然为弱联通块个数的平方。

得证。