平面图

就是放在平面上展开,存在一种画法能够使得图的边与边之间没有交点,这玩意就叫平面图。

但是一般来说吧,这个东西要配和着对偶图来使用。

对偶图

就是对于原平面图的每一条边,将与其接壤的两个面在对偶图中连一条边。特殊地,当且仅当对于一条边两边的面是同一个面,那么会出现自环。

然后不难发现,对偶图的对偶图是原图。

给出辅助用图。

(改自 百度百科,那里的图有一点点问题)

SB

一些性质

(要求有源汇点)平面图的最小割可以转化为对偶图的最短路。

然后要保证这么一条最短路要横跨源汇点所属的两个区域

题目

海拔

狼抓兔子