最小环
- 求无向图的最小环长度。
在无向图中最小环长度不小于 \(3\)。
使用 Floyd 算法，可以在带权图上跑，但是时间复杂度为 \(O(n^3)\)。
考虑 \(f[k][i][j]\) 为表示 \(i\) 经过 \(1\sim k\) 中的点到 \(j\) 的最短路（\(i,j\) 不一定小于 \(k\)）。
确定一个环至少需要三个点，我们考虑以 \(k\) 作为最大点，则 \(i,j\) 必须小于 \(k\)，由于边无向，我们可以钦定 \(i<j\)，最小环的属性：长度可以由 \(f[k-1][i][j]+w(j,k)+w(k,i)\) 计算出，实际意义为 \(j\to k\to i\to \cdots j\) 形式的环长。边求最短路边计算最小环长度。
枚举边。考虑枚举每一条边，计算若其作为环上一条边的最小环长。使用断边操作删去 \((u,v)\)，以 \(u\) 为源点，对于无权图跑 DFS 或 BFS 求出此时的 \(dis[v]\)，对于带权图跑 Dijkstra 或 SPFA，若存在路径，则环长为 \(w(u,v)+dis[v]\)，复杂度在无权图中为 \(O(m^2)\)，带权图中上界为 \(O(nm^2)\)。
枚举点。枚举在环上的点 \(i\)，对于无权图跑 BFS，通过 BFS 生成树计算出最小环，复杂度 \(O(n(n+m))\)。具体的，BFS 生成树满足任意图上一边 \((u,v)\)，两点深度之差不超过 \(1\)，即若正向搜索到非树边 \((u\to v)\)，构成环只有 \(dis[u]=dis[v]\) 和 \(dis[u]+1=dis[v]\) 两种可能，分别考虑即可，大小为 \(dis[u]+dis[v]+1\)。
- 求有向图的最小环长度。
有向图中最小环长度不小于 \(2\)。
考虑类似无向图的 Floyd，但由于边有向，\(i,j\in[1,k-1]\)，并且注意计算环长的式子下标顺序。
断边搜索或跑最短路和枚举点跑 BFS 依然可用，注意断边仅一条。
下面给出无向图中 Floyd 算法代码：P6175 可用 Floyd 或断边最短路算法跑过。
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i!=j)dis[i][j]=w[i][j]=1e9;
}
}
for(int i=1;i<=m;++i){
int u=read(),v=read(),W=read();
dis[u][v]=dis[v][u]=w[u][v]=w[v][u]=min(dis[u][v],W);//去重边
}
for(int k=1;k<=n;++k){
for(int i=1;i<k;++i){
for(int j=i+1;j<k;++j){
ans=min(ans,dis[i][j]+w[i][k]+w[j][k]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
if(ans==1e9)puts("No solution.");
else cout<<ans;
return 0;
}
- 其他算法求最小环大小
因为有些题目会在求最小环中加一些限制条件，从而优化求解复杂度。
如 P2661 [NOIP2015 提高组] 信息传递 规定了每个点出度一定为 \(1\)，可以使用并查集，拓扑排序，BFS，DFS 等方法过掉。
- 无向无权图最小环计数
\(n\leq 3\times10^3,m\leq 6\times 10^3\)
BFS 生成树。
图的传递闭包
bitset 优化可以理解为：若 \(i\) 能到 \(k\)，\(i\) 就能到 \(k\) 能到的所有点以及 \(i\) 原本能到的点。
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
if(f[i][k])f[i]|=f[k];
}
}