「BZOJ1997」[HNOI2010] Planar

2015年1月31日5,6193

Description

Input

Output

题解

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

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

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

 

avatar
2 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
975Likecerhcy Recent comment authors
  Subscribe  
提醒
975
975

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

hcy

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

Likecer

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