跳转至

最小环

问题

给出一个图，问其中的有 n个节点构成的边权和最小的环 (n\ge 3)是多大。

图的最小环也称围长。

暴力解法

设 u和 v之间有一条边长为 w的边， dis(u,v)表示删除 u和 v之间的连边之后， u和 v之间的最短路。

那么最小环是 dis(u,v)+w。

总时间复杂度 O(n^2m)。

Dijkstra

枚举所有边，每一次求删除一条边之后对这条边的起点跑一次 Dijkstra，道理同上。

时间复杂度 O(m(n+m)\log n)。

Floyd

最小环是自己到自己的距离，所以我们强迫最短路出去跑一遍就行了。

怎么强迫？

对于所有的 i，使它自己到自己的距离为 \infty，也就是

1
dis[i][i] = (1 << 30);

然后利用 Floyd 的性质，跑完之后对所有的 dis[i][i]取 \min即可。

时间复杂度： O(n^3)

例题

GDOI2018 Day2 巡逻

给出一张 n个点的无负权边无向图，要求执行 q个操作，三种操作

  1. 删除一个图中的点以及与它有关的边
  2. 恢复一个被删除点以及与它有关的边
  3. 询问点 x所在的最小环大小

对于 50\%的数据，有 n,q \le 100

对于每一个点 x所在的简单环，都存在两条与 x相邻的边，删去其中的任意一条，简单环将变为简单路径。

那么枚举所有与 x相邻的边，每次删去其中一条，然后跑一次 Dijkstra。

或者直接对每次询问跑一遍 Floyd 求最小环， O(qn^3)

对于 100\%的数据，有 n,q \le 400。

还是利用 Floyd 求最小环的算法。

若没有删除，删去询问点将简单环裂开成为一条简单路。

然而第二步的求解改用 Floyd 来得出。

那么答案就是要求出不经过询问点 x的情况下任意两点之间的距离。

怎么在线？

强行离线，利用离线的方法来避免删除操作。

将询问按照时间顺序排列，对这些询问建立一个线段树。

每个点的出现时间覆盖所有除去询问该点的时刻外的所有询问，假设一个点被询问 x次，则它的出现时间可以视为 x + 1段区间，插入到线段树上。

完成之后遍历一遍整棵线段树，在经过一个点时存储一个 Floyd 数组的备份，然后加入被插入在这个区间上的所有点，在离开时利用备份数组退回去即可。

这个做法的时间复杂度为 O(qn^2\log q)。

还有一个时间复杂度更优秀的在线做法。

对于一个对点 x的询问，我们以 x为起点跑一次最短路，然后把最短路树建出来，顺便处理出每个点是在 x的哪棵子树内。

那么一定能找出一条非树边，满足这条非树边的两个端点在根的不同子树中，使得这条非树边 +两个端点到根的路径就是最小环。

证明：

显然最小环包含至少两个端点在根的不同子树中一条非树边。

假设这条边为 (u,v)，那么最短路树上 x到 u的路径是所有 x到 u的路径中最短的那条， x到 v的路径也是最短的那条，那么 x\to u\to v\to x这个环肯定不会比最小环要长。

那么就可以枚举所有非树边，更新答案。

每次询问的复杂度为跑一次单源最短路的复杂度，为 O(n^2)​。

总时间复杂度为 O(qn^2)。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论