hdu7206

题目描述

给定一个平面图，求其对偶图的最小生成树

解题思路

我们首先考虑平面图欧拉公式的证明：

给出连通平面图的公式：

其中 表示顶点数， 表示边数， 表示面数。

我们经过研究可以发现，平面图的面被一个环包围，且该环内部不可能再有环，只可能有链。

针对这一性质，我们考虑用删边和删点的方法来求解。

首先我们从每条链的末端开始，删去所有的链边。考虑它对答案的贡献，删去一条链边不会改变面数，只会减少一个顶点和一条边。

接下来删去一条环边。考虑任意一个环的性质，对于任意一个环，它环上节点数和边数都相同，那么删去一条边之后，对于这个环而言还剩下 条边和 个顶点。

再考虑它对面的影响。我们任意删除一条环边，对于这个环上的所有节点而言，它们组成了一棵新的生成树，对于这个环而言，原本在该环内部的一个面与外部相连，面数 。我们回到平面图，我们删除环边的时候，选择作为网孔的环，每删除一条环边，面数 。

我们反复操作上述过程，可以得知，最后一个环断开时，必然会得到一棵树。那么这棵树删除所有的边之后会剩余一个顶点。同样，这棵树也处于1个面中，因此答案就呼之欲出了。

将这种情况拓展到一般平面图中。我们熟知，每个连通图对答案的贡献都为 。但是 个连通图共享一个外部的面，因此它们对答案的贡献为 。

有了如上的理论基础作为铺垫，我们回到本题。本题之中要求解对偶图的最小生成树。让我们考虑对偶图的最小生成树的性质，即将每一个面相联通所需要的最小边数的大小。

我们考虑上述的删边证明过程，面数减少与删除网孔上的一条环边紧密相关。进一步分析我们可以得到，只要删除一条环边，我们即可减少一个面。因此本题中，我们每次选择一条环边删除，即可得到最小生成树。

但是删除一条边要使用动态树的做法，不够优秀。我们考虑其逆过程，即在加边过程中进行统计。我们用一个并查集维护，如果加入一条环边，其必定会生成一个新的网孔，使得面数 。

本题中需要字典树最小的解，于是我们从后向前加边，对于每一个网孔而言，其最后加入的边一定是原图中该网孔最先被加入的边。