平面图对偶图-JZTXT

注意：博主并不会最小左转法！

什么是平面图：

如果能将一张图放到平面上并且边不相交，那么这张图就被称为平面图，比较常见的平面图就是网格图。

像这张图就是平面图：

但是这张图就不是平面图：

这条红边放到外面也会和 \((1,4)\) 这条边相交。

关于平面图的一些概念：

有限面：一张平面图将一个平面分成了很多个部分，面积是有限的部分被称为有限面。
无限面：同上，面积无限的部分被称为无限面。

比如这张图，面 \(2,3,4\) 都是有限面，而面 \(1\) 是无限面。

欧拉公式：\(\text{点数}-\text{边数}+\text{面数}=2\)。
常用性质：对于 \(n \ge 3\) 的联通简单平面图，有 \(m \le 3\cdot n-6\)，其中 \(n\) 是点数，\(m\) 是边数。

什么是对偶图：

有源汇：将源点和汇点用另一条边链接，将每个面看成点，两个相邻的面连边，边权是邻边的权值。

比如这张图：（设源点为 \(1\)，汇点为 \(5\)）

它的对偶图就是:

新图中源点为 \(1\)，汇点为 \(6\)。（因为这里多加了一条红边，所以有可能加不了，然后就寄了，但是一般题目都是用网格图，所以没啥事）

对偶图有非常神奇的性质：将每一条从源点到汇点的路径对应着一个割，至于为什么，大概就是你将经过的边全部割掉，对偶图上 \(S\) 和 \(T\) 就连通了，说明除了我加的红边之外没有路径能从平面图上的 \(S\) 到 \(T\) 了。

根据这个性质我们就能优化一些东西。

无源汇：只要不加上面那张图的红边就好了，割就是一个经过无限面的环。

若图为有向图，不难发现原图上的边权对应的是逆时针旋转 \(90^{\circ}\) 的边权，比如上面那张图，平面图上边 \((1,3)\) 对应的就是对偶图上的 \((4,6)\)，而 \((3,1)\) 则是 \((6,4)\)。

例题：

~~代码都在这里~~

洛谷 P4001 [ICPC-Beijing 2006] 狼抓兔子

这玩意就是一个最小割，但是直接流复杂度是 \(O(n^6)\) 的~~虽然能过，我谔谔~~。

首先这个图显然是平面图，题目又是让求最小割，考虑转成对偶图，对偶图上从起点到终点每一条路径都是一个割，所以最小割就是最短路，然后跑最短路就没了。（

洛谷 P3209 [HNOI2010] 平面图判定

首先发现边有那么多根本没用，\(m\) 大于 \(3\cdot n-6\) 的直接输出 \(NO\) 就好了。

将一条边拆成两个点，一个为这条边放到环内部，一个为这条边放到环外部，枚举两条边 \(i,j\) ，若他们能放到同一侧就不连边，否则就将 \(i\) 的放在环内部点和 \(j\) 的放在环外部点连起来，将 \(i\) 的放在环外部点和 \(j\) 的放在环内部点连起来，因为边是无向边，所以直接并查集就好了，不用 \(\text{2-sat}\)（这个处理的是有向图）。

这样时间复杂度就是 \(O(Tn^2)\) 的，可以通过，注意判相交的细节。

洛谷 P2046 [NOI2010] 海拔

发现我走太高并不优，这样只会徒加贡献，所以每个点高度只可能是 \(0,1\)，思考一下发现高度为 \(0\) 的和高度为 \(1\) 的一定是一个连通块，因为你考虑一个点周围高度全是 \(1\)，只有他是 \(0\)，不如直接把他高度也变成 \(1\)，这样一定不劣。

现在题目就被转化的很简单了，现在就等于给每个点求一个高度，使得对于每一条从起点到终点的路径高度变化且只变化一次，也就是我们将所有左右高度不一样的边割掉，起点终点不连通，现在我们就转化成了最小割了，建对偶图直接跑就行了。

洛谷 P7916 [CSP-S 2021] 交通规划

首先先思考一下 \(k=2\) 怎么做，不难发现这个跟上面那个海拔是一毛一样的，就是将白点看成高度为 \(0\)，黑点看成高度为 \(1\)。

考虑怎么推广这个东西，首先有一个很暴力的直接优化，就是直接在原图上跑最小割，拼上上面的 \(k=2\)，这样就可以得到 \(80pts\) 了。

其实还有一个 \(k=3\)，这个也挺有用的。（但是部分分没给）

因为流没有前途，所以还是从对偶图角度考虑。

不难发现一定有两个颜色相同，并且他俩一定相邻，就比如说下图：

假设原图是黄框，我们把黑色附加点看成红色点，白色附加点看成蓝色点，现在我们把网格图向外扩充一圈，现在将图标号，最外层的编号是按绿线分割的，编号完也就是下图：（~~其实上面的文字解释我自己都看不懂~~）

考虑怎么将红蓝点断开，不难发现就是让 \(1,2\) 成为对偶图源汇点。

同理，如果有很多红点很多蓝点，但是所有红点都相邻，也可以让”左边和红点相邻，右边和蓝点相邻“的面作为源点，让”左边和蓝点相邻，右边和红点相邻“（这里的左右都是按照射线编号顺序编号的左右，例如上图中的 \(2\) 为到达面，这个不是肉眼看的左右）的面作为汇点直接跑最短路。

正解：

现在你什么性质都没有了?，但是不难从上面的得出，我要是相同颜色的点相邻是没有任何用的（同 \(k=3\)，所以下面不考虑这种情况），我们定义”左边和红点相邻，右边和蓝点相邻“的面为出发面，”左边和蓝点相邻，右边和红点相邻“的面为到达面，首先这两种面的数量肯定一样，考虑我们给他们配对，还是按题目中给的射线编号顺序方法给所有出发面到达面重标号，假设我们将编号为 \(l\) 的面和编号为 \(r\) 的面匹配（这里要求两个面不是同一种面），不妨假设 \(l\) 为出发面，我们直接跑从 \(l\) 到 \(r\) 的最短路，然后把所有最短路上的边割掉，发现这个操作使得 \(l,r\) 内所有的蓝点都到达不了这个 \(l\) 左边相邻的红点了，就比如下图：

你的 \(l\) 是右上角的红点到右上角的蓝点，\(r\) 是左下角的蓝点到右边的另一个红点，你这样建图不会像橙边这样割，因为上面那个蓝点还是能到达右上角的红点，但是可以像粉边这样割，然后你发现你这样分出来的一定是正确的，因为你考虑一个 \(1,4\)，\(2,3\) 的配对方法（下图），你在中间留的是一样颜色的点，割出去的是颜色一样的点，归纳一下就行了。