Sightseeing Trip

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2198 字
Floyd逐点统计最小环并还原节点路径
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1494
// 题意：n<=100 的无向图，求至少含 3 个点、点不重复且边权和最小的环，输出环上节点顺序，无解输出 No solution.
// 思路：Floyd 逐层加入中转点 k，先用只含前 k-1 个中转点的最短路 d[i][j] 配合边 i-k、k-j 更新最小环，再用 k 松弛 d，路径由 pre 数组还原。
// 复杂度：O(n^3) 时间 / O(n^2) 空间
// 易错点：必须先用 k 统计环再用 k 更新 d，顺序颠倒会算错；环要求三点互异，枚举时限定 i<j<k 即可保证。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int a[MAXN][MAXN];
int d[MAXN][MAXN];
int pre[MAXN][MAXN];
vector<int> path;
void getPath(int i, int j){
    if(pre[i][j] == 0) return;
    getPath(i, pre[i][j]);
    path.push_back(pre[i][j]);
    getPath(pre[i][j], j);
}
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = INF;
            d[i][j] = INF;
        }
        a[i][i] = 0;
        d[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        if(z < a[x][y]) a[x][y] = a[y][x] = z;
        d[x][y] = a[x][y];
        d[y][x] = a[y][x];
    }
    int ans = INF;
    for(int k = 1; k <= n; k++){
        for(int i = 1; i < k; i++){
            for(int j = i + 1; j < k; j++){
                if(d[i][j] >= INF || a[i][k] >= INF || a[k][j] >= INF) continue;
                if(d[i][j] + a[i][k] + a[k][j] < ans){
                    ans = d[i][j] + a[i][k] + a[k][j];
                    path.clear();
                    path.push_back(i);
                    getPath(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][k] + d[k][j] < d[i][j]){
                    d[i][j] = d[i][k] + d[k][j];
                    pre[i][j] = k;
                }
            }
        }
    }
    if(ans >= INF){
        cout << "No solution." << '\n';
        return 0;
    }
    int st = 0;
    for(size_t i = 1; i < path.size(); i++){
        if(path[i] < path[st]) st = (int)i;
    }
    for(size_t t = 0; t < path.size(); t++){
        if(t) cout << ' ';
        cout << path[(st + t) % path.size()];
    }
    cout << '\n';
    return 0;
}
Sightseeing Trip

正文

一本通·提高篇的其它内容
