「BZOJ1997」[HNOI2010] Planar

2015年1月31日4,2233

Description

Input

Output

题解

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

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

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

 

说点什么

提醒
avatar
975
975

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

hcy

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

Likecer

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