[Baltic2007]Escape逃跑问题

sgu评测机傲娇了一天TAT
继续回来颓废bzoj
题解不负责任预警

description

给你个矩形,矩形里面有若干个圆(可能与矩形相交)
我们要删掉最少的圆,使得能够有一条曲线,满足从左下角出发,到右上角,并且不与任何圆相交

sol

原始想法:

这个其实可以看成最短路?跨越一个圆就代表走了一个边权为1的边,然后搞出从左下角到有右上角的最短路就可以了……
可是这个怎么构图啊QAQ

接下来的想法

不会做,不会做……(:з」∠)

接下来的想法

这不就是一个裸的最小割么凑!
还是太naive……有曲线不能从左下到右上等价于,有一条从左上到右下的曲线,满足曲线一直在圆内或矩形边界上
那么我们删除最小的圆,使得左上到右下不连通即可
然后就是网络流的事了

灵感来自delayyy的这篇博文

Comments

comments powered by Disqus