【bzoj1997】[Hnoi2010]Planar

2015年1月31日3,2433

Description

Input

Output

题解

用平面图m<=3n-6的性质剪枝条

若两条边在圆内相交,则他们在圆外也是相交的,即若a,b不能同时取,a’,b’也不能同时取

按2-sat建模缩点后判断合法性

 

  • hcy2015年9月26日 下午10:38 回复

    学长,传说[Hnoi2010]Planar可以用带权并查集做,可以教一下不?

    #1  
    • Likecer2015年10月6日 下午11:51 回复

      不是带权的, 直接并查集就可以. 因为你可以看到这里加的其实都是无向边.

      #11
  • 9752016年7月25日 下午7:34 回复

    为什么相交的情况不包含圆内两条边共点?

    #2