最小环

参考资料

• 最小环 - OI Wiki

简介

最小环（girth）是图中边权和最小的简单环，至少含 3 个顶点。稠密图用 Floyd 在 $O(n^3)$ 内求解，稀疏图可枚举边后跑 Dijkstra。

Floyd 算法

Floyd 在求全源最短路的同时可以顺带求出最小环。关键性质：在外层循环枚举中间节点 $k$ 之前，$dis_{i,j}$ 表示仅经过编号在 $[1,k)$ 中节点的 $i\to j$ 最短路。因此，在第 $k$ 次外层迭代开始时，对所有满足 $i<k,j<k$ 的点对，

$$dis_{i,j}+g_{i,k}+g_{k,j}$$

就是以 $k$ 为最大编号节点的环的长度（$g$ 为原始邻接矩阵）。枚举并取最小值即得最小环。时间复杂度 $O(n^3)$。

925 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=305;
const ll inf=0x3f3f3f3f3f3f3f3fll;
ll g[N][N],dis[N][N];
int n;
ll min_cycle()
{
	ll ans=inf;
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<k;i++)
		{
			for(int j=1;j<i;j++)
			{
				if(g[i][k]<inf&&g[k][j]<inf&&dis[i][j]<inf)ans=min(ans,g[i][k]+g[k][j]+dis[i][j]);
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(dis[i][k]<inf&&dis[k][j]<inf)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			g[i][j]=dis[i][j]=(i==j?0:inf);
		}
	}
	while(m--)
	{
		int u,v;
		ll w;
		cin>>u>>v>>w;
		g[u][v]=g[v][u]=min(g[u][v],w);
		dis[u][v]=dis[v][u]=min(dis[u][v],w);
	}
	ll ans=min_cycle();
	if(ans==inf)cout<<"No solution."<<'\n';
	else cout<<ans<<'\n';
	return 0;
}

Dijkstra 算法

依次枚举每条边 $(u,v,w)$，临时删去该边后从 $u$ 跑一次 Dijkstra，得到不经过该边的 $u\to v$ 最短路 $d$，则过该边的最小环长度为 $d+w$。时间复杂度 $O(m(n+m)\log n)$，适合稀疏图。

例题

洛谷 P6175 无向图的最小环问题

给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。