对偶图

对偶图是建立在原有的平面图上的。

对于为什么叫**对偶**图，先看下度娘对于对偶的解释：
>对偶是用字数相等、结构相同、意义对称的一对短语或句子来表达两个相对应或相近或意思相同的修辞方式。

自己可以看完对偶图的建图之后再来琢磨下这个句子，脑补一下**对偶图**的**对偶**

好了，说正事。

---

这是一张对偶前的平面图

![pic](http://imglf0.ph.126.net/fuB277Jd_Yr40Rtu8Z3ckA==/6631392121633991370.png)

红线组成的是它的对偶图

什么？不知道怎么画？

就是把面变成点，相邻的面连边。（所以每一条边都会跨国原有边界。）

so,我们现有一个平面图

![pic](http://imglf2.ph.126.net/kj7Qmp8hD_ImFSg3UCma3g==/6631443798680500106.png)

然后再找出图上所有面（还有最外面无限大的面）

![pic](http://imglf2.ph.126.net/6yZOaiD6AwyVZyIqpCWbBg==/6631319553866554736.png)

然后，把面看成点

![pic](http://imglf1.ph.126.net/Cse1uaEp81btyMuz6SryWQ==/6598290224622986734.png)

就像之前说的，相邻的面连边，蓝色与红色和紫色还有灰色相连（只有一个定点相同的不算，如绿色和蓝色）

![pic](http://imglf0.ph.126.net/NaH3D0XTi6r7AFuglgHNmw==/6598300120227636714.png)

然后连下去

![pic](http://imglf2.ph.126.net/-BF-2mufopUZ1VAulw2XDw==/6598227552460205960.png)

就画好了

那么有什么用呢

比如最小割之类的啊

![pic](http://imglf0.ph.126.net/Oy3RfbW8pDLLQ_A9wLAMdg==/6598143989576494419.png)

如果左上和右下分别为源点（S）和汇点（T），那么如果我们把外侧无限大的面分成两个 半面，（忽略无限大面自己之间的连线），构造对偶图，那么对偶图中灰蓝色点到灰紫色点的的任意一条路径都是原图的一个割。

因为对偶图中的边会跨过切只会跨过原图中的一条边。所以就可以在最短路的时间内跑最小割了。

例题[传送门](http://www.lydsy.com/JudgeOnline/problem.php?id=2007)

wuvin