最小环学习笔记

图上最小的环

概述

最小环问题,又称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