• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2-SAT 学习笔记

开发技术 开发技术 1周前 (07-19) 10次浏览

对于若 (A)(B),连边 (Ato B)

故可推出:

(A) 一定成立,连边 (neg Ato A)

(A) 一定不成立,连边 (Ato neg A)

(A)(B),连边 (neg Ato B,neg Bto A)

(A)(B),即 (A) 一定成立、 (B) 一定成立。

(A) 异或 (B),连边 (Ato neg B,neg Ato B,Btoneg A,neg Ato B)

云云……

然后跑一次 Tarjan,如果 (col_A=col_{neg A}) 则无解。

如果有解,(col_A>col{neg A})(A) 为真,否则为假。


程序员灯塔
转载请注明原文链接:2-SAT 学习笔记
喜欢 (0)