观光之旅

AcWing-344-观光之旅

分析

见《进阶指南》第361页。

无向图的最小环问题。

实现

#include <iostream>
#include <cstring>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long LL;
const int N = 110;
int n, m;
int g[N][N], dis[N][N], rec[N][N];
vector<int> path;

void get_path (int x, int y) { // x_next -> ... -> y_prev
    if (rec[x][y] == 0) return;

    get_path(x, rec[x][y]);
    path.push_back(rec[x][y]);
    get_path(rec[x][y], y);
}

int main () {
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; ++ i) g[i][i] = 0;
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; ++ i) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    int res = inf;
    memcpy(dis, g, sizeof(g));
    for (int k = 1; k <= n; ++ k) { // floyd
        for (int i = 1; i <= k - 1; ++ i) {
            for (int j = i + 1; j <= k - 1; ++ j) {
                if ((LL)dis[i][j] + g[j][k] + g[k][i] < res) {
                    res = dis[i][j] + g[j][k] + g[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 (dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    rec[i][j] = k;
                }
            }
        }
    }

    if (res == inf) {
        printf("No solution.");
    } else {
        for (int i = 0; i < path.size(); ++ i)
            cout << path[i] << ' ';
    }
    return 0;
}