本文从WordPress迁移而来, 查看全部WordPress迁移文章
2-sat判定
题意:a和b玩剪刀石头布,玩n轮,b的出拳已经全部给出来,1,2,3分别是石头,布,剪刀。下面给出m行表示a出拳的一下限制,每行的格式为ith jth k,k为0表示ith轮和jth轮a要出一样的拳,k为1表示要出不一样的。问能不能给a安排一套出拳的方法,使得a在n轮里都不会输,不会输包括了平局或者赢。可以保证不输,输出yes,否则no
参考题解:http://www.cnblogs.com/ambition/archive/2011/11/09/Eliminate_the_Conflict.html
- a每一轮可以出3种拳,每种拳对应2种状态,即出或不出。所以一轮里面拆出了6个点。
- 单纯考虑a自己的出拳情况,可以知道一个简单的事实,a每一轮只可能出一种拳。所以每一轮了,出了石头不能出布和剪刀,出了布不能出石头和剪刀,出了剪刀不能出石头和布。这一点和b无关,也和a本身的那些限制关系无关,所以一开始就可以加上这些必然关系,即加上这些边
- 目的是保证了a不输,所以要考虑b每一轮的出拳。
如果b出了石头,a只能出石头和布,必然关系就是,a不出石头就出布,不出布就出石头
如果b出了布,a只能出布和剪刀,必然关系是,a不出布必出剪刀,不出剪刀必出布
如果b出了剪刀,a只能出剪刀和石头,必然关系是,a不出剪刀必出石头,不出石头必出剪刀 - 考虑a自身的那些限制条件
- ith和jth轮要出相同的拳:ith出了石头jth必出石头,反过来一样。ith出了布jth必出布,反过来一样。ith出了剪刀jth必出剪刀,反过来一样
- ith和jth不能出一样的拳:ith出了石头jth必不出石头,反过来一样………………….
这样,所有的限制关系够建好了,就求一次scc,可以判定了
1 |
|