poj3207专题

[POJ3207]Ikki's Story IV - Panda's Trick(2-SAT)

题目大意: 圆上顺序排列n个点,现要在一些点间连边,边只能在圆内或圆外,求有没有可能不相交 学习了2-SAT! 参考资料如下: 1、神犇写的巨无敌详细的博客 2、我觉得很好看的懂的论文 好的那么我来捋一捋2-SAT的思路,首先对于一个选择进行拆点分成选和不选,对于约束关系,如果选了a不能选b的话,那就a向b的对称点连边。建图之后强联通缩点,如果有一对对称点在同一个连通分量那就说明无解

[POJ3207]Ikki's Story IV - Panda's Trick

poj3207-Ikki’s Story IV - Panda’s Trick 题面 liympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki and winning so many times, he is tired of such easy games