题解里并没有这种做法,我个人也还没实现所以问一下。
首先我们可以认为一对情侣互相限制。
假设 (u,v)(u, v)(u,v) 互相限制,那么就是 u=1→v=2u=1\rightarrow v=2u=1→v=2、u=2→v=2u=2\rightarrow v=2u=2→v=2、v=1→u=2v=1\rightarrow u=2v=1→u=2、v=2→u=1v=2\rightarrow u=1v=2→u=1 的经典 2-SAT\text{2-SAT}2-SAT 模型。
然后发现相邻三个人至少有一个人吃的不一样也可以抽象为另一个 2-SAT\text{2-SAT}2-SAT 模型,即 x,x+1x, x+1x,x+1 相同 →\rightarrow→ x+1,x+2x+1,x+2x+1,x+2 不同 …\dots…。然后又可以出来一组解 。
然后对于这组解扔到第一个 2-SAT\text{2-SAT}2-SAT 里处理出最终解。
是否可行?