> 给定一个无向图，求图中至少包含 $3$ 个点的环。 ### Dijkstra 令 $dis(u,v)$ 表示不经过边 $(u,v)$ 时 $u$ 和 $v$ 之间的最短路，$w$ 为 $u$ 和 $v$ 之间的边长。 无向图的最小环为 $\min(dis(u,v)+w)$ 有向图的最小环为 $\min(dis(v,u)+w)$ 枚举每条边，删除这条边后跑一遍 Dijkstra ，计算答案如上。 时间复杂度：$O(m(n+m)\log n)$ ### Floyd 我们在做 Floyd 时最外层循环 $k$ 表示经过前 $k$ 个的时的最短路。 假设一个换上有相邻的三个点：$u<->w<->v$ 则环长为 $u$ 到 $v$ 不经过 $w$ 的最短路 $+$ $val(u,w)+val(v,w)$ 对于任意一个环，假设上面编号最大的点为 $w$ ，与其相邻的点为 $u$ 和 $v$ ，则在循环到 $k=w$ 之前，我们已经求出了从 $u$ 到 $v$ 不经过点 $w$ 的最短路，只要再加上它们到 $w$ 的距离，即为这个环环长。 思想和 Dijkstra 的类似，这样也可以满足每个还都被算到。 我们只要在每次循环 $k$ 时，计算出所有满足 $i<k,j<k$ 的点对 $(i,k,j)$ 的答案即可。 时间复杂度：$O(n^3)$，两种方法各有优劣，当 $m$ 较小时 Dijkstra 更快。 #### CODE ```cpp memcpy(dis, val, sizeof dis); for (int k=1; k<=n; k++) { for (int i=1; i<k; i++) for (int j=i+1; j<k; j++) ans=min(ans, dis[i][j]+val[i][k]+val[k][j]); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]); } ``` ### [观光之旅](https://www.acwing.com/problem/content/346/) > 给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。 > > 该问题称为无向图的最小环问题。 > > 你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。 > > $1\le n\le 100$ > > $1\le m\le 10^5$ 板子题，需要记录答案，只需记录 $dis[i][j]$ 是由哪个状态转移过来的即可。 $n$ 较小，$m$ 较大，只有 Floyd 跑得过。 ```cpp #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #include <vector> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e2+10; int n, m, val[N][N], dis[N][N], pos[N][N], ans=2e9; vector<int> p; void dfs(int i, int j) { int k=pos[i][j]; if (!k) return; dfs(i, k); p.push_back(k); dfs(k, j); } void update(int i, int j, int k) { p.clear(); p.push_back(k); p.push_back(i); dfs(i, j); p.push_back(j); } int main() { n=read(), m=read(); memset(val, 10, sizeof val); memset(dis, 10, sizeof dis); for (int i=1; i<=n; i++) dis[i][i]=0; for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); val[x][y]=val[y][x]=dis[x][y]=dis[y][x]=min(val[x][y], z); } for (int k=1; k<=n; k++) { for (int i=1; i<k; i++) for (int j=i+1; j<k; j++) if (dis[i][j]+val[i][k]+val[k][j]<ans) { ans=min(ans, dis[i][j]+val[i][k]+val[k][j]); update(i, j, k); } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (dis[i][k]+dis[k][j]<dis[i][j]) { dis[i][j]=dis[i][k]+dis[k][j]; pos[i][j]=k; } } if (ans>=1e8) puts("No solution."); else for (int i:p) printf("%d ", i); return 0; } ``` Loading... > 给定一个无向图，求图中至少包含 $3$ 个点的环。 ### Dijkstra 令 $dis(u,v)$ 表示不经过边 $(u,v)$ 时 $u$ 和 $v$ 之间的最短路，$w$ 为 $u$ 和 $v$ 之间的边长。 无向图的最小环为 $\min(dis(u,v)+w)$ 有向图的最小环为 $\min(dis(v,u)+w)$ 枚举每条边，删除这条边后跑一遍 Dijkstra ，计算答案如上。 时间复杂度：$O(m(n+m)\log n)$ ### Floyd 我们在做 Floyd 时最外层循环 $k$ 表示经过前 $k$ 个的时的最短路。 假设一个换上有相邻的三个点：$u<->w<->v$ 则环长为 $u$ 到 $v$ 不经过 $w$ 的最短路 $+$ $val(u,w)+val(v,w)$ 对于任意一个环，假设上面编号最大的点为 $w$ ，与其相邻的点为 $u$ 和 $v$ ，则在循环到 $k=w$ 之前，我们已经求出了从 $u$ 到 $v$ 不经过点 $w$ 的最短路，只要再加上它们到 $w$ 的距离，即为这个环环长。 思想和 Dijkstra 的类似，这样也可以满足每个还都被算到。 我们只要在每次循环 $k$ 时，计算出所有满足 $i<k,j<k$ 的点对 $(i,k,j)$ 的答案即可。 时间复杂度：$O(n^3)$，两种方法各有优劣，当 $m$ 较小时 Dijkstra 更快。 #### CODE ```cpp memcpy(dis, val, sizeof dis); for (int k=1; k<=n; k++) { for (int i=1; i<k; i++) for (int j=i+1; j<k; j++) ans=min(ans, dis[i][j]+val[i][k]+val[k][j]); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]); } ``` ### [观光之旅](https://www.acwing.com/problem/content/346/) > 给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。 > > 该问题称为无向图的最小环问题。 > > 你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。 > > $1\le n\le 100$ > > $1\le m\le 10^5$ 板子题，需要记录答案，只需记录 $dis[i][j]$ 是由哪个状态转移过来的即可。 $n$ 较小，$m$ 较大，只有 Floyd 跑得过。 ```cpp #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #include <vector> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e2+10; int n, m, val[N][N], dis[N][N], pos[N][N], ans=2e9; vector<int> p; void dfs(int i, int j) { int k=pos[i][j]; if (!k) return; dfs(i, k); p.push_back(k); dfs(k, j); } void update(int i, int j, int k) { p.clear(); p.push_back(k); p.push_back(i); dfs(i, j); p.push_back(j); } int main() { n=read(), m=read(); memset(val, 10, sizeof val); memset(dis, 10, sizeof dis); for (int i=1; i<=n; i++) dis[i][i]=0; for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); val[x][y]=val[y][x]=dis[x][y]=dis[y][x]=min(val[x][y], z); } for (int k=1; k<=n; k++) { for (int i=1; i<k; i++) for (int j=i+1; j<k; j++) if (dis[i][j]+val[i][k]+val[k][j]<ans) { ans=min(ans, dis[i][j]+val[i][k]+val[k][j]); update(i, j, k); } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (dis[i][k]+dis[k][j]<dis[i][j]) { dis[i][j]=dis[i][k]+dis[k][j]; pos[i][j]=k; } } if (ans>=1e8) puts("No solution."); else for (int i:p) printf("%d ", i); return 0; } ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏