最小环学习笔记

发表于 | 评论数： | 阅读次数：

图上最小的环

概述

最小环问题，又称The Shortest Circle.

是指在一个图中，有n个节点构成的边权和最小的环($n \geq 3​$)，一般来说,最小环分为有向图最小环和无向图最小环。

也就是在一张图上从一个点出发,经过一条简单路径回到起点成为环.图的最小环就是所有环中长度最小的。

解决方法

最小环问题有好几种解决方法。

朴素算法求最小环

朴素算法就非常简单了。

首先令$min(i,j)$表示删除$e(i,j)$这条边之后$i$到$j$的最短路。

那么最小环的长度就是$min(u,v) + e(u,v)$。

时间复杂度：$O(EV^2)$。

带权并查集求最小环

例题：LuoguP2661

Solution

本题中要求求的是有向图最小环。

我们把每一位同学看成一个节点，分别向他们信息传递的对象连有向边，那么问题就转化成了最小环。

这里我们用带权并查集来解决问题。

假如说第$i$号同学的信息传递对象是第$j$号同学，那么连一条有向边$e(i,j)$。

同时，我们更新$i$号点到其父节点的路径，$i$节点到其父节点的路径长即为$j$号点到其父节点的路径长+1。

那么这样建完图之后，游戏的轮数就是这张图中最小环的长度。

如果两个点祖先节点相同，那么显然它们可以构成一个环，这时我们更新最小环长度。

对当前最小环长度和这两个点到其祖先节点长度之和+1取个$min$即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 2e5 + 10;
int UFS[MAXN],dist[MAXN],Minc = INT_MAX;
int n,t;
/* functions */
inline int Find(int x){
    if(x == UFS[x])return x;
    else{
        int last = UFS[x];
        UFS[x] = Find(UFS[x]);
        dist[x] += dist[last];
    }
    return UFS[x];
}
inline void unionx(int x,int y){
    int findx = Find(x);
    int findy = Find(y);
    if(findx != findy){UFS[findx] = findy; dist[x] = dist[y] + 1;}
    else Minc = std::min(Minc,dist[x] + dist[y] + 1);
}
int main(int argc,char *argv[]){
    scanf("%d",&n);
    FOR(i,1,n,1) UFS[i] = i;
    FOR(i,1,n,1){
        scanf("%d",&t); unionx(i,t);
    }
    printf("%d\n",Minc);
    return 0;
}

Floyd求最小环

顾名思义，在Floyd的同时，顺便算出最小环。

Floyd算法在求解最短路时，最外层的循环保证了当循环到$k$时，所有节点都已经求得$0 … k-1$为中间点的最短路。

我们知道，一个环至少由$3$个节点构成。

假设某一个环中编号最大的节点为$k$，在环中与之左右相连的点的编号为$i,j$。

那么最大编号为$k$的最小环长度为$Minc = dist_{i,j} + Graph_{i,k} + Graph_{k,j}$。

其中$dist_{i,j}$表示以$0…k-1$号点为中间点时的最短路径。

这时，我们会发现：这刚好符合Floyd算法最外层循环到$k$时的情况，则此时对$i,j$循环所有编号小于$k$的顶点组合即可找到最大编号为$k$的最小环。

然后再经过最外层循环,即可找到整个图的最小环。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Minc = inf;
for(int k=1;k<=n;k++){
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k;j++)//环上的两个点必然是不同的
            Minc = std::min(Minc,dist[i][j]+Graph[i][k]+Graph[k][j]);
        	//上文求最小环的公式，k为环的最大编号点
	}
    for(int i=1;i<=n;i++){//Floyd最短路
        for(int j=1;j<=n;j++){
            if(dist[i][j] > dist[i][k] + dist[k][j])
                dist[i][j] = dist[i][k] + dist[k][j];
		}
	}
}

例题： HDU1599

非常简单的最小环模板题。

注意初始化的时候要把$dist$和$Graph$数组设置为无穷大(即避免自环)。

最后注意一下输入格式即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
	}
}
inline void read(int &x){
	int rt = FastIO::getint();
	x = rt;
}
inline void print(int x,bool enter){
	FastIO::putint(x);
	FastIO::flush();
	FastIO::space(enter);
}
/* definitions */
const int inf = INT_MAX;
const int MAXN = 8e2 + 10;
int minc,n,m;
int dist[MAXN][MAXN],Graph[MAXN][MAXN];
/* functions */
inline void Floyd(){
	minc = inf;
	FOR(k,1,n,1){
		FOR(i,1,k,1){
			FOR(j,i+1,k,1)
				minc = std::min(minc,dist[i][j] + Graph[i][k] + Graph[k][j]);
		}
		FOR(i,1,n,1){
			FOR(j,1,n,1){
				if(dist[i][j] > dist[i][k] + dist[k][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
}
inline void init_Graph(){
	FOR(i,0,MAXN-1,1){
		FOR(j,0,MAXN-1,1)
			Graph[i][j] = dist[i][j] = inf;
	}
}
int main(int argc,char *argv[]){
	while(scanf("%d%d",&n,&m) != EOF){
		init_Graph(); 
		int x,y,z;
		FOR(i,1,m,1){
			scanf("%d%d%d",&x,&y,&z);
			if(Graph[x][y] > z){
				Graph[x][y] = Graph[y][x] = z;
				dist[x][y] = dist[y][x] = z;
			}
		}
		Floyd();
		if(minc >= inf) printf("It's impossible.\n");
		else printf("%d\n",minc);
	}
	return 0;
}

THE END