526互联

无向图的最小环问题

发布时间 2023-05-31 19:52:55作者: Chen_jr

考试时候记错方法，然后还有其他一堆错误然后寄掉了。

你TM学了个JB。

所以写一篇

无向图的最小环问题

解法一，\(floyd\), \(O(n ^ 3)\)

for(int k = 1; k <= n; ++k){
	for(int i = 1; i < k; ++i)if(k != i)
		for(int j = i + 1; j < k; ++j)if(i != j && j != k){
			if(mp[i][k] + mp[k][j] + dis[i][j] < len){
				len = mp[i][k] + mp[k][j] + dis[i][j];
				ans = f[i][j];
			}else if(mp[i][k] + mp[k][j] + dis[i][j] == len){
				ans += f[i][j];
			}
		}
	for(int i = 1; i <= n; ++i)if(k != i)
		for(int j = 1; j <= n; ++j)if(i != j && j != k){
			if(dis[i][j] > dis[i][k] + dis[k][j]){
				dis[i][j] = dis[i][k] + dis[k][j];
				f[i][j] = f[i][k] * f[k][j];
			}else if(dis[i][j] == dis[i][k] + dis[k][j]){
				f[i][j] += f[i][k] * f[k][j];
			}
		}
}

解法二，最短路

枚举一条边，删去它，跑两个点的最短路，更新答案

根据最短路的实现方式有不同的复杂度

一些拓展，（或许某些只适用于边权都为 \(1\) 的情况）

一种做法，枚举一个点，然后 \(BFS\)，在访问到之前访问过的点时候进行更新

需要注意的是，严格做法应该为从根出发的不同边对应的子树染上不同的颜色，对于连接两个不同颜色的边进行更新

但是由于找最小环，不染色得到的非法方案一定不是最优解，所以一般不管

比如今天 \(T1\)

这个东西能跑的更快

做法是按照度数从大到小枚举点，从该点出发 \(BFS\)， 两个剪枝

  1. 深度大于已经找出的最小环长度的一半（上取整）直接返回

  2. 之前当过根的点删去，不再进行 \(BFS\)

随机数据下接近线性，卡的话目前只有卡到根号的方法，详情咨询 \(Kaguya\)