bzoj 1001 [BeiJing2006]狼抓兔子

Posted by

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=1001

题解

首先这道题是裸的最大流,但是如果直接套用最大流算法明显会TLE,我们可以利用本题的特殊性质来解决。

有关概念

(摘自浅析最大最小定理在信息学竞赛中的应用
平面图的性质:

  1. 如果一个连通的平面图有$latex n$个点,$latex m$条边和$latex f$个面,那么$latex f=m-n+2$;

  2. 对于每一个平面图$latex G$,都有一个对偶图$latex G’$与之对应:
    图$latex G$一个面为图$latex G’$中的一个点;
    图$latex G$中一条边:
    若属于两个面,图$latex G’$中两个面所对应的点之间连边;
    若只属于一个面,图$latex G’$中构造那个面所对应的点连向自己的回边。
    于是:$latex G$和$latex G’$边数相同,$latex G’$中的环与$latex G$中的割一一对应。

样例
平面图$latex G$

对偶图$latex G’$

S-T平面图:图中的一个点为源点$latex S$,另一个点为汇点$latex T$,且$latex S$和$latex T$都在图中无界面的边界上。

求解方法

先对原图进行一些改造:
在图$latex G$中$latex S$和$latex T$之间连一条边,将原来的无界面分成两部分。
再构造对偶图,将图$latex G$中两个无界面在图$latex G’$中对应的两个点分别视为$latex S’$和$latex T’$,两个点之间不连边;
构造样例的对偶图:

可以发现一个$latex S’$到$latex T’$之间的路径对应图$latex G$的一个割,再考虑容量的话就可以发现$latex S’$-$latex T’$的最短路即是原图的最小割。
最后利用最大流-最小割定理求得答案。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注