BZOJ 1001 – 「BJOI2006」狼抓兔子

题目链接:BZOJ 1001

题目要在一张$n \times m (n, m \leq 10^3)$的网格图上求最小割。考虑到数据范围,点的个数高达$10^6$数量级,直接跑Dinic会超时,我们需要利用这个网格图是“S-T平面图”的性质。在周冬的《两极相通——浅析最大最小定理在信息学竞赛中的应用》一文中,介绍过平面图转对偶图求最小割的方法,即平面图中的最小割等于对偶图中的最短路。

我们把平面图上的被边分割开来的区域称为面,则可以这样建图:

  • 连接平面图的$S$和$T$,边权为$+\infty$,将原来外面的空白区域区域分成了两块,对应对偶图中的$S*$和$T*$两个点
  • 对于平面图中的边$e$,属于面$F$和$G$,则对偶图中$F*$和$G*$连边,边权为$e$的边权
  • (这一点在本题中用不到)对于平面图中的边$e$,只属于面$F$,则对偶图中$F*$和$F*$连边,边权为$e$的边权

 

说点什么

avatar
50
  Subscribe  
提醒