口胡出来一种两次 2-SAT 的解法,不知可不可行?
查看原帖
口胡出来一种两次 2-SAT 的解法,不知可不可行?
66511
DPair楼主2020/11/24 22:24

题解里并没有这种做法,我个人也还没实现所以问一下。

首先我们可以认为一对情侣互相限制。

假设 (u,v)(u, v) 互相限制,那么就是 u=1v=2u=1\rightarrow v=2u=2v=2u=2\rightarrow v=2v=1u=2v=1\rightarrow u=2v=2u=1v=2\rightarrow u=1 的经典 2-SAT\text{2-SAT} 模型。

然后发现相邻三个人至少有一个人吃的不一样也可以抽象为另一个 2-SAT\text{2-SAT} 模型,即 x,x+1x, x+1 相同 \rightarrow x+1,x+2x+1,x+2 不同 \dots。然后又可以出来一组解 。

然后对于这组解扔到第一个 2-SAT\text{2-SAT} 里处理出最终解。

是否可行?

2020/11/24 22:24
加载中...