跳转至

最小环

问题

给出一个图,问其中的有 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)logn)

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 数组的备份,然后加入被插入在这个区间上的所有点,在离开时利用备份数组退回去即可。


评论