最小环问题
1. 最小环定义:
-
最小环是指在一个图中,有
n
个节点构成的边权和最小的环(n>=3)
。 -
一般来说,最小环分为有向图最小环和无向图最小环。
2. 最小环算法
-
Dijkstra
解法- 设
u
和v
之间有一条边长为w
的边,dis(u,v)
表示删除u
和v
之间的连边之后,u
和v
之间的最短路。 - 那么最小环是枚举每一条边,并删除此条边后,以其中一个端点为起点跑一边单源最短路最小环的值为:
min(dis(u,v)+w)
- 时间效率为:\(O(m*n*log\ n)\) ,对稠密图来说边数 \(m\) 趋近 \(n^2\), 所以时间效率为 \(O(n^3log\ n)\)。
- 设
-
Floyd
解法- 记原图
u,v
之间边权为mp(u,v)
,floyd
算法在外层循环到第k
个点时(还没开始第k
次循环),最短路数组dis
中,dis(u,v)
表示的是从u
到v
且仅经过编号[1,k)
区间中的点的最短路。 - 最小环至少有三个顶点,设其中编号最大的顶点编号为
w
,环上与w
相邻两侧的两个点为u,v
,则在最外层循环枚举到k=w
时,该环的长度为dis(u,v)+mp(v,w)+mp(w,u)
,所以在循环时候i,j
只需枚举到i<k,j<k
更新答案即可。 - 复杂度:\(O(n^3)\)
- 记原图
3. 例题
-
find the mincost route(hdu1599)
Description
- 杭州有
N
个景区,景区之间有一些双向的路来连接,现在8600想找一条旅游路线,这个路线从A
点出发并且最后回到A
点,假设经过的路线为\(V_1,V_2,....V_K,V_1\),那么必须满足\(K>2\) ,就是说至除了出发点以外至少要经过2
个其他不同的景区,而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线,并且花费越少越好。
Input
- 第一行是
2
个整数N
和M(N <= 100, M <= 1000)
,代表景区的个数和道路的条数。 - 接下来的
M
行里,每行包括3
个整数a,b,c
.代表a
和b
之间有一条通路,并且需要花费c
元(c <= 100)
。
Output
- 对于每个测试实例,如果能找到这样一条路线的话,输出花费的最小值。如果找不到的话,输出
It's impossible.
。
Sample Input
3 3 1 2 1 2 3 1 1 3 1 3 3 1 2 1 1 2 3 2 3 1
Sample Output
3 It's impossible.
Hint
- 有可能存在重边,保留权值最小那条。
Code
#include <bits/stdc++.h> #define Inf 0x3f3f3f3f typedef long long LL; const int maxn=100+5; LL dis[maxn][maxn],mp[maxn][maxn]; //注意开longlong int n, m; void Init(){ for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) mp[i][j] = i == j ? 0 : Inf; } void Solve(){ while(~scanf("%d%d", &n, &m)){ Init();//多组数据注意初始化 for (int i = 0; i < m; i++){ int u, v; LL w; scanf("%d%d%lld", &u, &v, &w); if (w < mp[u][v])//处理重边,保留权值小的 mp[v][u] = mp[u][v] = w; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = mp[i][j];//初始化两点间的距离 LL ans = Inf; for (int k = 1; k <= n; k++){//枚举中间点 for (int i = 1; i < k; i++)//枚举k的其中一个相邻点 for (int j = i + 1; j < k; j++)//枚举k的另一相邻点 ans = std::min(ans, dis[i][j] + mp[i][k] + mp[k][j]); //上面暂时不能以k为中间点更新dis[i][j],如果更新可能不是环 for (int i = 1; i <= n; i++)//k无用了,可以用来更新 for (int j = 1; j <= n; j++) dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]); } if (ans == Inf) printf("It's impossible.\n"); else printf("%lld\n", ans); } } int main(){ Solve(); return 0; }
- 杭州有
4. 总结
- 求最小环问题我们一般用
Floyd
,相较于Dijskra
,Floyd
更简单且高效 - 对有有向图的最小环问题,我们直接用
Floyd
跑一遍最短路,然后遍历一遍1~n
,求出min(dis[i][i])
即可,显然初始是dis[i][i]=Inf
。 - 并查集、
Tarjan
均可求环,但他们只能求只有简单环的图,对有切环、套环的图无法求最小环。 - 要想求图中节点最少的环,我们可以把边权设为1,然后用
Floyd
求最小环。