CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可，转载请注明：“转自 【算法】最小环”
前言
- 本文将介绍有关有向图/无向图求解最小环长的算法。
前置知识
- 图论基础（概念）
- 广度优先搜索/BFS
- 最短路算法（dijkstra, floyd）
最小环
- 问题描述：在一个图 $G = (E, V)$ 中求最小环长。边权非负。
-
在本文中，记 $N = V $, $M = E $。
Floyd求解最小环
无向图的求解
- 在 Floyd 算法执行前，预设 $dis(u,u)=+\infty$；
- 然后执行 Floyd 算法，所有 $dis(u,u)$ 中的最小值即为所求。
有向图的求解
- 和无向图稍有区别的是，Floyd 算法会把形如 $\langle u,v\rangle, \langle v, u \rangle$ 的路径看作环，所以可能会经过同一条边两次。
- 对于这个问题，我们考虑先处理所有包含重边和自环的环。去除重边和自环后，每个环至少包含 3 个点。不妨设环上标号最大的点为 $u$, 与 $u$ 相邻的两个点分别为 $v_1, v_2$。考虑 Floyd 算法中枚举中转点的过程，当最外层循环枚举完 $1, 2, \dots u - 1$ 时，该环上除了边 $\langle v_1, u \rangle, \langle u, v_2\rangle$ 以外的边都已经被 Floyd 算法考虑到。此时用 $dis(v_2, v_1) + w(v_1, u) + w(u, v_2)$ 去更新最小环的答案。通过这种方式遍历所有三元组 $(u, v_1, v_2)$，即可求解最小环长。
代码实现
for(int k = 1; k <= n; k++) {
for(int i = 1; i < k; i++)
for(int j = i + 1; j < k; j++) //注意i!=j
ans = min(ans, f[i][j] + M[i][k] + M[k][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
f[i][j] = f[j][i] = min(f[i][j], f[i][k] + f[k][j]);
}
- 算法复杂度为 $O(N^3)$。
基于最短路树求解最小环
- 最短路树：原图的一棵生成树，每条树边都在某条（单源）最短路上。
- 该定义对有向图和无向图均适用。在下面的证明中，不妨假设图为连通图。
- 先处理所有重边和自环。枚举每个点作为根 $r$ 求出一棵最短路树，对于每条非树边$\langle u, v\rangle$，若 $u$ 到 $v$ 的路径经过 $r$，则用 $dis(r,u) + dis(r,v) + w(u,v)$ 更新答案。
- 算法正确性证明：
- 命题 1：若 $u$ 为 $v$ 的祖先，则 $u$ 到 $v$ 的树上路径为 $u, v$ 间的最短路。（正确性显然）
- 命题 2：若树根在最小环上，则它恰有一条边不在最短路树上。
- 证明：若命题 2 为假，则环上至少有两条边不在最短路树上。删去这两条边可以把环上的点分为不能通过最短路树连通的两个子集。不妨设树根 $r$ 所在部分为 $S$，另一部分为 $T$。由最短路树是原图的一棵生成树知，必然存在一条由树边构成的简单路径连通 $S, T$。记该路径的端点为 $u, v$，$u\in S, v\in T$。则 $r$ 是 $u$ 的祖先，而 $u$ 是 $v$ 的祖先。由命题 1，用 $u, v$ 间的树上路径去替换最小环上 $u$ 到 $v$ 的一条路径，可以得到一个更小的环。矛盾。
- 由命题 2，枚举每个点作为树根，即可求得最小环。
- 注：如果需要感性理解可以略过证明。
- 对于 $\sum w(u,v) \leq m$ 的图（一般为边权全为 1），BFS求最短路树，判断两个点的 LCA 是否为根，单次搜索可以做到 $O(m)$，总复杂度 $O(nm)$，优于 Floyd 算法。
- 对于更加一般的图，需要用单源最短路算法求最短路树。总复杂度 $O(nm \log n)$，在稠密图中劣于 Floyd 算法。
代码实现
- 本题无法使用 Floyd 算法。笔者在考场上欲采用 Floyd 算法，构造了一个错误的处理方式，导致没有在赛时通过本题。
正确代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pi;
typedef long long LL;
const int P = 998244353;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e6 + 5;
int n, m, ans = INF;
vector <int> E[N];
set <pi> S;
int vis[N], dis[N];
namespace math {
int minp[N], prime[N], p_cnt;
void prime_table(int n) {
p_cnt = 0;
for(int i = 1; i <= n; i++) minp[i] = i;
for(int i = 2; i <= n; i++) {
if(minp[i] == i) prime[++p_cnt] = i;
for(int j = 1; prime[j] <= minp[i]; j++) {
if(j > p_cnt) break;
if(1ll * i * prime[j] <= n) minp[i * prime[j]] = prime[j];
else break; //important
}
}
}
};
using namespace math;
void bfs(int s) {
int flag = 0;
queue <pi> Q;
Q.push(make_pair(s, -1));
vis[s] = true;
while(Q.empty() == false) {
int u = Q.front().first, pre = Q.front().second;
Q.pop();
for(auto v: E[u]) {
if(v == pre) continue;
if(vis[v] == false) {
if(u == s) vis[v] = ++flag;
else vis[v] = vis[u];
dis[v] = dis[u] + 1;
Q.push(make_pair(v, u));
}
else if(vis[u] != vis[v]) {
ans = min(ans, dis[u] + dis[v] + 1);
}
}
}
}
void init() {
int u, v, x;
scanf("%d", &n);
prime_table(1e6);
for(int i = 1; i <= n; i++) {
scanf("%d", &x);
u = minp[x];
if(u != 1) {
int flag = 0;
while(x % u == 0) x /= u, flag ^= 1;
if(!flag) u = 1;
}
v = minp[x];
if(v != 1) {
int flag = 0;
while(x % v == 0) x /= v, flag ^= 1;
if(!flag) v = 1;
}
if(u == v) return (void) printf("1\n");
if(u > v) swap(u, v);
if(S.count(make_pair(u, v))) ans = 2;
else S.insert(make_pair(u, v));
E[u].push_back(v);
E[v].push_back(u);
}
prime[0] = 1;
for(int i = 1; i <= 1000; i++) {
if(minp[i] != i) continue;
for(int i = 0; i <= p_cnt; i++) vis[prime[i]] = dis[prime[i]] = 0;
bfs(i);
}
if(ans < INF) printf("%d\n", ans);
else printf("-1\n");
}
int main() {
//ios::sync_with_stdio(false);
init();
return 0;
}
错误处理方式：
fpd = lower_bound(prime + 1, prime + Index + 1, 1000) - prime;
for(int i = fpd; i <= Index; i++) {
for(auto u: E[i])
for(auto v: E[i])
if(u < v) {
if(M[u][v] == 1) return (void) printf("3\n");
if(M[u][v] == 2) ans = 4;
M[u][v] = M[v][u] = min(M[u][v], 2);
}
}
/*
把形如<小, 大>, <大, 小>的路径压成了长度为2的一条边。
但是会导致三个大长度为2的路径构成一个长度为6的不合法环。
所以像这种压边一般都是不靠谱的...
*/
Author: Fanfaredash
