acwing-344. 观光之旅

发表于 2024-04-26 分类于 acwing 阅读次数： Waline：本文字数： 656 阅读时长 ≈ 2 分钟

考点

最短路
最小环问题
Floyd的路径输出

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 50;
int n, m, a[maxn][maxn], d[maxn][maxn], pos[maxn][maxn];
ll ans = 0x3f3f3f3f;
vector<int> path;

// 中序遍历输出路径
void get_path(int i, int j) {
  if (pos[i][j] == 0) return;
  get_path(i, pos[i][j]);
  path.push_back(pos[i][j]);
  get_path(pos[i][j], j);
}

void floyd() {
  for (int k = 1; k <= n; ++k) {
    // 遍历两个小于k的节点
    for (int i = 1; i < k; ++i) {
      for (int j = i + 1; j < k; ++j) {
        if ((ll)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);
        }
      }
    }
    // floyd代码，并记录中间点
    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;
        }
      }
    }
  }
}

int main() {
  cin >> n >> m;
  memset(a, 0x3f, sizeof(a));
  for (int i = 1; i <= n; ++i) a[i][i] = 0;
  for (int u, v, w, i = 1; i <= m; ++i) {
    cin >> u >> v >> w;
    a[u][v] = a[v][u] = min(a[u][v], w);
  }
  memcpy(d, a, sizeof(a));
  floyd();
  if (ans == 0x3f3f3f3f)
    cout << "No solution.";
  else
    for (auto it : path) cout << it << " ";
  return 0;
}

思路

之所以题目规定了至少包含3个点的环，是因为无向图的边本身就是双向的，a -> b自然也可以b -> a，显然这不是一个环，但是却可以回到原点，所以强制设定至少包含3个点。

如果是有向图的情况下，枚举起点s = 1 ~ n，执行堆优化的Dijkstra算法求解单源最短路径，每个s一定是第一个被从堆中取出的节点，扫描s的所有出边，当扩展、更新完成后，令d[s] = 正无穷，然后继续求解。当s第二次被从堆中取出时，说明绕回了点s，那么d[s]就是经过点s的最小环长度。

考虑floyd算法的过程，当外层循环k刚开始时，d[i, j]保存着经过编号不超过k - 1的节点从i到j的最短路长度。

显然，\(\min_{1\leqslant i<j<k} \left\{ d\left[ i,j \right] +a\left[ j,k \right] +a\left[ k,i \right] \right\}\)就是满足以下两个条件的最小环长度。