平面图转对偶图




在写网络流的时候我们会遇到一些题,网格之类的图,网络流跑不过,于是搜了一下题解,发现这些题必须要经过一种名叫”平面图转对偶图”的处理,然后跑遍最短路就可以直接AC。本篇博客即介绍平面图转对偶图。


现在我们可以先来了解一下什么是”平面图”,”什么是对偶图”(引自LuoguID:duyi)

我们引入对偶图的概念
前置概念:
平面图:指点和边之间有一种连法使得边与边之间没有交点

如上图,黑色的图是平面图,而红色的图不是。


这是就可以把平面图的每一个封闭区域看成一个点,如果原图中两个封闭区域有交边就在新图中两个点之间连一条边,值得注意的是,整个平面图外面的区域也是”封闭区域”(即s和t两点)。这样得到一张新的图,就是我们说的对偶图。


由于原图是平面图,所以任意一条边左右都有两个封闭区域,在对偶图中一定有一条边,所以原图中的边一定在对偶图中有一条对应的边。


现在直接给结论:如果我们给原平面图加上源点和汇点,那么原图的最大流就是其对偶图源点到汇点的最短路。


好吧,其实以上我觉得都是废话
平面图转对偶图非常简单:
把整个平面图视为若干个由线和线包围的区块
每个区块你给编个号,有公共边的区块连条边,边权为那条公共边的边权
然后把源点和汇点连条边,这条边圈出的新区块以及整个图外的区块分别设为新图的源点汇点
于是你就可以愉快地写最短路了。


例题:
[NOI2010]海拔
[ICPC-Beijing 2006]狼抓兔子


以下就以上面两道题作为例子较详细地展示一下如何建图

[NOI2010]海拔

就拿样例讲讲


图一是根据样例建成的平面图
图二是该平面图的对偶图(黑色边是旧边,蓝边是新边,红点是新点)
我们可以发现对偶图的每一条边都跟平面图上对应的边相割
直接上结论:
无向图则直接建双向边,有向图则需要根据源点汇点的方向改变有向边在新图的方向
有了这个样例入门,可以看看下面那道题

[ICPC-Beijing 2006]狼抓兔子


<!––!>
坑先放着…明天再写。



点我回到主页

平面图转对偶图》有2个想法

  1. Pingback引用通告: [NOI2010]海拔 – TaK-Vin

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s