洛谷 P10927. Sightseeing trip

问题描述

link

分析

题目要求：给定一张 $n$ 个点、$m$ 条边的无向图（两点之间可能有重边），找出一个包含至少 3 个不同顶点的简单环，使环上边权和最小，并输出环上顶点的访问顺序；若图中不存在这样的环，输出 No solution.。

关键观察：一个简单环总可以看成"两条相邻的边 $u\to k$、$k\to v$"加上"$u$ 到 $v$ 的一段路径"拼成。如果 $u$ 到 $v$ 的那段不是最短路，把它换成最短路就能得到一个不更长的环，所以最小环一定由两条边加上 $u\to v$ 的最短路组成。问题就变成：枚举"环上编号最大的顶点 $k$"和它的两个邻居 $i,j$，求 $i\to j$ 只经过编号小于 $k$ 的点的最短路，再补上两条边。

思路：Floyd 求最小环 + 路径还原

设 $a$ 为原图邻接矩阵，$d$ 为最短路矩阵。Floyd 外层循环枚举到 $k$ 时（此时还没有用 $k$ 更新过最短路），$d[i][j]$ 恰好是从 $i$ 到 $j$ 且只经过编号 $<k$ 的中间点的最短路。于是：

环 $i\to \cdots \to j\to k\to i$ 的长度为 $d[i][j]+a[j][k]+a[k][i]$，其中 $1\le i<j<k\le n$。

算法流程：

1. 读入邻接矩阵 $a$：初始化 $a[i][i]=0$，重边取最小值；把 $a$ 拷贝给 $d$。
2. 外层枚举 $k=1\dots n$：
   • 先枚举 $1\le i<j<k$，用 $d[i][j]+a[j][k]+a[k][i]$ 更新最小环答案，并记录当前最优环；
   • 再用 $k$ 作为中间点做 Floyd 松弛：$d[i][j]=min(d[i][j],d[i][k]+d[k][j])$，同时记录 $pos[i][j]=k$ 表示这次更新。
3. 若 $ans$ 仍是无穷大，说明图中没有环，输出 No solution.；否则输出记录的环。

正确性：任意一个环都有唯一的"编号最大的顶点" $k$，环上其余顶点编号都小于 $k$。当外层循环枚举到 $k$ 时，$d[i][j]$ 不超过该环去掉 $k$ 后的那段路径长度（那段路径只经过小于 $k$ 的点），所以这个环会被一个不劣于它的候选环覆盖；反过来，$d[i][j]$ 对应的路径不经过 $k$，加上两条边后 $i\to j\to k\to i$ 一定是顶点互不重复的合法简单环。因此对所有候选环长取最小值就是全局最小环。

路径还原：$pos[i][j]=k$ 表示 $i\to j$ 的最短路经过了 $k$。get_path(x, y) 递归输出 $x\to y$ 最短路上的中间顶点：先递归 $x\to pos[x][y]$，输出 $pos[x][y]$，再递归 $pos[x][y]\to y$。找到更小环时，把顶点序列 $i$、$i\to j$ 的中间点、$j$、$k$ 依次存入答案即可。

实现细节：

• 比较答案时用 long long，防止 $d[i][j]+a[j][k]+a[k][i]$ 在 $d$ 为无穷大时溢出；
• 枚举 $i<j$ 既避免重复，又保证环包含 $i,j,k$ 三个互不相同的顶点，符合"至少 3 个点"的定义；
• 重边取最小值即可，两点之间的多条边不会影响最小环。

复杂度：$O(n^3)$ 时间、$O(n^2)$ 空间，本题 $n\le 100$、$m\le {10}^4$，完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;

int a[310][310], d[310][310], pos[310][310];
int n, m, ans = 0x3f3f3f3f;
vector<int> path;

void get_path(int x, int y) {
    if (pos[x][y] == 0) return ;
    get_path(x, pos[x][y]);
    path.push_back(pos[x][y]);
    get_path(pos[x][y], y);
}

int main() {
    cin >> n >> m;

    memset(a, 0x3f, sizeof a);
    for (int i = 1; i <= n; i++) a[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        a[x][y] = a[y][x] = min(a[x][y], z);
    }

    memcpy(d, a, sizeof a);
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                if ((long long )d[i][j] + a[j][k] + a[k][i] < ans) {
                    ans = d[i][j] + a[j][k] + a[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(i, j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    pos[i][j] = k;
                }
            }
        }
    }

    if (ans == 0x3f3f3f3f) {
        puts("No solution.");
        return 0;
    }

    for (int i = 0; i < path.size(); i++) cout << path[i] << " ";
    cout << endl;

    return 0;
}