[NOI2017]游戏

题解:

容易发现这应该是个2-sat

发现除了x每个点都只有两个点

x<=8 是特判

怎么判?

最暴力的是3^8枚举一下

考虑把它也搞在2-sat上,那么只需要枚举它一定不是a,一定不是b就可以了(c不用枚举了因为那两种包含了所有情况了)

这样复杂度就是2^8*m的

然后就变成了2-sat输出方案

只需要先缩点再在DAG上倒着连边就好了

代码:

原文地址:https://www.cnblogs.com/yinwuxiao/p/8481612.html