基本介紹
- 中文名：最小環
- 領域：計算機科學
定義,套用,解決方法,樸素算法,傳統的解決方法：dijkstra,floyd求最小環,例題講解,Description,Input,Output,Sample Input,Sample Output,Hint,分析:,標程,
定義
從一個點出發,經過一條簡單路徑回到起點成為環.圖的最小環就是所有環中長度最小的。
套用
最小環問題一般出現在計算機科學領域，主要是解決競賽中的一些有關最小環的題目。
解決方法
樸素算法
令e(u,v)表示u和v之間的連邊，再令min(u,v)表示，刪除u和v之間的連邊之後，u和v之間的最短路
最小環則是：min(u,v) + e(u,v)
時間複雜度是EV
傳統的解決方法：dijkstra
任意一個環的權值，我們都可以看成兩個有邊相連的結點i、j的直接距離加上i、j間不包含邊(邊i-＞j)的最短路徑。求最短路徑我們第一個想到的就是Dijkstra算法。而Dijkstra所求的是一個點到所有點的最短距離。用Dijkstra所求的i、j的最短距離一定是i、j的直接距離(如果i，j連通)，所以我們需要先將i、j的邊從圖中刪除(若i，j不連通，則不用刪除)，再用Dijkstra求新圖中i、j的最短距離即可。所以我們每次在圖中選取一條邊，把它從圖中刪掉．然後對刪掉的那條邊所對應的2點進行Dijkstra，也就是m次Dijkstra
floyd求最小環
在Floyd的同時，順便算出最小環。
Floyd算法保證了最外層循環到 k 時所有頂點間已求得以 0...k-1 為中間點的最短路徑。一
個環至少有 3 個頂點,設某環編號最大的頂點為 L ,在環中直接與之相連的兩個頂點編號
分別為 M 和 N (M,N ＜ L),則最大編號為 L 的最小環長度即為 Graph(M,L) + Graph(N,L) +
Dist(M,N) ,其中 Dist(M,N) 表示以 0...L-1 號頂點為中間點時的最短路徑,剛好符合 Floyd
算法最外層循環到 k=L 時的情況,則此時對 M 和 N 循環所有編號小於 L 的頂點組合即
可找到最大編號為 L 的最小環。再經過最外層 k 的循環,即可找到整個圖的最小環。
int mincircle = infinity;
Dist = Graph;
for(int k=0;k<nVertex;++k){
//新增部分:
for(int i=0;i<k;++i)
for(int j=0;j<i;++j)
mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);
//通常的 floyd 部分:
for(int i=0;i<nVertex;++i)
for(int j=0;j<i;++j){
int temp = Dist[i][k] + Disk[k][j];
if(temp < Dist[i][j])
Dist[i][j] = Dist[j][i] = temp;
}
}
上面是對無向圖的情況
若是有向圖,只需稍作改動。注意考慮有向圖中 2 頂點即可組成環的情況
例題講解
Description
杭州有 N 個景區， 景區之間有一些雙向的路來連線， 現在 8600 想找一條旅遊路線， 這個路線從 A 點出發並且最後回到 A 點。
假設經過的路線為 V1,V2,....VK,V1,那么必須滿足 K＞2,就是說至除了出發點以外至少要經過 2 個其他不同的景區， 而且不能重複經過同一個景區。 現在 8600 需要你幫他找一條這樣的路線， 並且花費越少越好。
Input
第一行是 2 個整數 N 和 M（ N ＜= 800, M ＜= 600000）， 代表景區的個數和道路的條數。
接下來的 M 行里， 每行包括 3 個整數 a,b,c.代表 a 和 b 之間有一條通路， 並且需要花費c 元(c ＜= 10000)。
Output
如果能找到這樣一條路線的話， 輸出花費的最小值。 如果找不到的話， 輸出 "It'simpossible." (沒有雙引號)
Sample Input
輸入樣例1：
3 3
1 2 1
2 3 1
1 3 1
輸入樣例2：
3 3
1 2 1
1 2 3
2 3 1
Sample Output
輸出樣例1：
3
輸出樣例2：
It's impossible.
Hint
對於 40%的數據： 2 ＜= n ＜ 100, m＜=10000
對於 100%的數據： n ＜= 800, m＜=600000
分析:
加入有一個環,其編號最大的點為 L,那么這個環可以看為 L 與其相鄰的兩個點 A 和
B 與 A 到 B 的最短路上的點(編號均小於 L 的最短路)。
考慮 floyd 算法,由於該算法每次都是求出了 1 到 k−1 做為中間點的最短路然後來求已 k 為
中間點的最短路,則我們可以將其拓展到求最小環
標程
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=810;
const int INF=214748364;
int gi[MAXN][MAXN];
int map[MAXN][MAXN];
int n,m;
int ans=INF;
int main()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
{
if( i==j )
gi[ i ][ j ]=map[ i ][ j ]=0;
else
gi[ i ][ j ]=map[ i ][ j ]=INF;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if( map[ a ][ b ]>c )
gi[ a ][ b ]=map[ a ][ b ]=gi[ b ][ a ]=map[ b ][ a ]=c;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=k-1;i++)
for(int j=i+1;j<=k-1;j++)
ans=min( ans,gi[ i ][ k ]+gi[ k ][ j ]+map[ i ][ j ]);
for(int i=1;i<=n;i++)
for(int j=1;j<=i-1;j++)
if( j!=k && i!=k )
map[ j ][ i ]=map[ i ][ j ]=min( map[ i ][ k ]+map[ k ][ j ],map[ i ][ j ]);
}
if( ans>=INF )
printf("It's impossible.\n");
else
printf("%d\n",ans);
return 0;
}
