Bakser's Blog

我是逗比。

bzoj1997 2-sat

| Comments

此题略神
当然平面图判定是有O(N)算法的,但那个算法太神我不会。
所以说亮点就在哈密尔顿回路上了。
一个环里外是对称的。
就是说两条路若在环里边必定有交点,那在环外边也是,否则把在环外边的对称到环里边不就是一个没有交点的可行解了吗。
所以说判断两条路在环内部有无交点,若有的话那这两条路就只能一个在里面一个在外面。
转化为2-sat问题。
正常捉就可以了。
代码太丑不发了.

Comments

comments powered by Disqus