[CF 343E]Pumping Stations解题报告

题目翻译


题解

首先,有一个东西叫Gomory-Hu(戈莫里-胡)树。就是说,对于一张题中这样的图可以建出来一棵树,使得图中s~t的最小割等于树中s~t路径上的最小边权。

那么问题来了:怎么建树呢?

有两篇资料:
Wiki百科:

yangff的博客:

如果你看完之后还不知道怎么建,不用担心,你不是一个人……

其实这个建树过程写出来并不难,看一下代码就知道了。大致思路是:一开始所有点都在同一个集合内。然后每次选一个集合,对其中两个点做最小割,按照源汇集分割这个集合,并添加一条边。最后所有集合都剩下一个点,树也就建完了。共需要做O(n)次最大流。

现在有了这棵树,应该怎么办呢?

很简单:选择树中权值最小的边,那么最优解一定是先在一侧走完,再经过这条边,再走另外一侧(只经过该权值最小的边一次,最优方案必然如此)。然后分成两部分递归下去即可。

所以这篇题解的核心其实是贴一下Gomory-Hu树的代码,相信我,代码真的非常简单……

代码

建树就是build_tree函数。


发表评论

电子邮件地址不会被公开。 必填项已用*标注