Q7.4.1.2. 奇怪的方格涂色 题解

原题链接

首先想到暴力网络流：考虑最小割，\(S\) 表示染黑色，\(T\) 表示染白色。

每个格子 \(i\)，连 \((S,i,b_i)\)，\((i,T,w_i)\)。怎么处理“奇怪的方格”？连 \((i,i^\prime,p_i)\) 和 \((i^\prime,j,+\infty)\)。表示如果 \(i\) 归属于 \(S\)（染黑色），那么就只能忍受奇怪所带来的 \(p_i\)，或者让 \(j\) 都不归属于 \(T\)。

答案即 \(\sum w+\sum b-\text{最小割}\)。

怎么优化建图？\(j\) 是满足 \(1\le j<i\) 且 \(l_i\le a_j\le r_i\)。那么离散化后用主席树，于是把满足这些条件的 \(j\) 拆成几个主席树上的点 \(x,y,\cdots\)，连 \((i^ \prime,x)\cdots\)。当然，要有主席树上每条边都是 \(+\infty\)。