AcWing 344. 观光之旅

题目传送门

一、Floyd求最小环

(\(Floyd\)) \(O(n^3)\)

设环的形式是：\(i<->k<->j\) , \(i<–>j\) （i\(,j,k\)不同）

\(floyd\)是典型的插点算法，每次插入点\(k\)，为此，在点\(k\)被[插入前]可计算\(i->j->k\)这个环
即此时中间节点为：\(1~k-1\)，即我们已经算出了任意\(i<->j\)的最短道路，中间经过的节点可以为 \((1,2,3,…,k-1)\)
我们只需枚举所有以\(k\)为环中最大节点的环即可。

\(pos[i][j]:i~j\)的最短路中经过的点是\(k\)(即由这个状态转移过来)，且这个\(k\)是此路径中编号最大的点(除\(i,j\))//根据\(Floyd\)算法实质决定
这条道路存在以下两条性质
1.在\(i~j\)的最短道路中，一定没有环(显然)
2.设\(i,j\)之间的最短道路经过点\(k\)(不同于\(i,j\))，则\(i~k , k~j\)之间必然没有交集

二、实现代码

#include 
using namespace std;
// 使用Floyd求最小环的经典题
const int N = 110; //稠密图，最多100个顶点，10000条边
const int INF = 0x3f3f3f3f;
typedef long long LL;
LL res = INF;     //最小环的长度，因为是多条路径的和，可能大于INT_MAX
int g[N][N];      //邻接矩阵，存储任意两点间的 "直接距离"
int d[N][N];      //邻接矩阵，存储任意两点间的 "最短距离"
int pos[N][N];    //记录i~j的最短距离是由k做为中间点获取到的
vector path; //最小环的组成点有哪些
int n, m;         // n行m列的二维矩阵

// i->j之间的路，输出i到j之间不包括i和j的道路
void dfs(int i, int j) {
    int k = pos[i][j];  // 中间转移点
    if (k == 0) return; // 没有转移点返回
    dfs(i, k);          // 递归计算i~k之间的路径
    path.push_back(k);  // k
    dfs(k, j);          // 递归计算k~j之间的路径
}

//获取 i->k->j-->i的环路径
void get_path(int i, int j, int k) {
    path.clear();
    path.push_back(k); //边界
    path.push_back(i);
    dfs(i, j); // k->i-->j->k
    path.push_back(j);
}

int main() {
    cin >> n >> m; // n个点，m条边

    memset(g, 0x3f, sizeof g);               //任意两点间距离正无穷
    for (int i = 0; i < n; i++) g[i][i] = 0; //自己和自己是距离为0的

    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c); //保留最短边
    }

    memcpy(d, g, sizeof d); //原图

    for (int k = 1; k <= n; k++) {
        //至少包含三个点的环所经过的点的最大编号是k
        //当枚举到k时，其实现在g数组中保存的是前k-1条边时的多原最短路径
        //如果引入k点，则可能的环路径长度为g[i][j] + d[i][k] + d[k][j]
        // d:直接路径
        // g:最短路径长度（经过Floyd计算过的最短路径）
        for (int i = 1; i < k; i++) //至少包含三个点，i，j，k不重合
            for (int j = i + 1; j < k; j++)
                if (res > (LL)g[i][j] + d[i][k] + d[k][j]) { //最小环
                    res = g[i][j] + d[i][k] + d[k][j];
                    get_path(i, j, k); // i->k->-j-->i为最小环，需要记录一下路径
                }
        //原始版本Floyd
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                    pos[i][j] = k; //这里比原始版本Floyd多了一步记录任意两点是通过k进行转移的
                }
    }
    //如果没有被修改过，则返回不存在最小环
    if (res == INF)
        cout << "No solution." << endl;
    else {
        //输出路径
        for (auto x : path) cout << x << ' ';
        cout << endl;
    }
    return 0;
}