python/TangDou/AcWing_TiGao/T3/Floyd/344.md

AcWing 344. 观光之旅

一、题目描述

给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为 无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式 第一行包含两个整数 N 和 M，表示无向图有 N 个点，M 条边。

接下来 M 行，每行包含三个整数 u，v，l，表示点 u 和点 v 之间有一条边，边长为 l。

输出格式 输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

二、floyd + dp求最小环模板题

最优化问题，从集合角度考虑(DP)，将所有环按编号最大的点 分成 n 类，求出每类最小，最后在类间取 min

分类的标准是 可重、不漏。（对于求数量的问题，分类的标准是 不重不漏）

集合划分

对于最大编号是 k 的所有环，记点 k 逆时针方向的前一点为 i，顺时针方向的下个点为 j。由于 dis[i,k]=g[i,k], dis[k,j]=g[k,j] 为定值，要使整个环最小，就要使 dis[i,j] 最小。

floyd 第一层循环到 k 时的 dis[i,j] 恰好是中间点只包含 1\sim k−1 的最短距离。因此第 k 类最小值可在此时得到。

状态表示

求方案

DP 求方案一般要 记录转移前驱的所有维。但 floyd 转移方程中的 k 表示路径的中间点，由于路径可以被两端和中间点覆盖，只要记下中间点，就能递归出路径。

三、floyd+dp+递归输出路径

#include <cstring>
#include <iostream>

using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], d[N][N];
int path[N], idx;
int mid[N][N];

void get_path(int i, int j) {
    int k = mid[i][j];          //获取中间转移点
    if (!k) return;             //如果i,j之间没有中间点，停止
    get_path(i, k);             // i->k
    path[idx++] = k;            //记录k节点
    get_path(k, j);             // k->j
}

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

    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i++) g[i][i] = 0;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int ans = INF;
    memcpy(d, g, sizeof d);
    for (int k = 1; k <= n; k++) {
        //插入DP计算
        /*
        Q:为什么循环的时候i和j都需要小于k啊，Floyd不是只需要经过的点小于k就可以了吗
        A:只是为了避免经过相同的点，比如i == k时，三个点就变成两个点了。
        其实循环到n也是可以的，不过当i, j, k中有两个相同时就要continue一下
        */
        for (int i = 1; i < k; i++)
            for (int j = i + 1; j < k; j++)

                if (g[j][k] + g[k][i] < ans - d[i][j]) {
                    ans = d[i][j] + g[j][k] + g[k][i];

                    //找到更小的环，需要记录路径
                    //最小环的所有节点（按顺序输出）
                    //下面的记录顺序很重要：
                    // 1. 上面的i,j枚举逻辑是j>i,所以i是第一个
                    // 2. i->j 中间的路线不明，需要用get_path进行探索
                    // 3. 记录j
                    // 4. 记录k
                    idx = 0;
                    path[idx++] = i;
                    get_path(i, j); // i是怎么到达j的？就是问dist[i,j]是怎么获取到的，这是在求最短路径过程中的一个路径记录问题
                    path[idx++] = j;
                    path[idx++] = 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];
                    mid[i][j] = k; //记录路径i->j 是通过k进行转移的
                }
    }

    if (ans == INF)
        puts("No solution.");
    else
        for (int i = 0; i < idx; i++) cout << path[i] << ' ';

    return 0;
}

四、关于三个INF相加爆INT的应对之道

Q1：为什么这里是用ans-dis[i,j],而不是写成 ans> dis[i,j]+g[j,k]+g[k,i]? A: g[j][k],g[k][i] ∈ l,l是小于500的,所在 g[j][k]+g[k][i]<1000,肯定没问题 dis[i,j]的初始值是INF，g[i,j]的初始值也是INF,如果都写在左边，如果i,j,k三者之间没有边，就是三个INF,累加和会爆掉INT,就会进入判断条件，错误. 而两个INF相加不会爆INT(想想松弛操作~)

Q2:(LL) dis[i][j] + g[j][k] + g[k][i] < ans 为什么是正确的？而 (LL) (dis[i][j] + g[j][k] + g[k][i]) < ans为什么就是错误的？ A: INT_MAX = 2147483647 LONG LONG MAX=9223372036854775807ll

INF = 0x3f3f3f3f = 1061109567 INF * 3 =1061109567 * 3 = 3183328701 大于INT_MAX，即会爆INT，需要开LONG LONG

(LL)a + b + c 将a转为LL,然后再加b加c,都是LL+int,在LL范围内，结果正确 (LL)(a + b + c) 是先计算a+b+c,先爆INT，再转换LL,结果错误。

Q3: 所有数据全开LL为什么一样不对呢？ A:

memset(q, 0x3f, sizeof q);
cout << q[0] << endl;     // 4557430888798830399
cout << q[0] * 3 << endl; //-4774451407313060419

因为问题出在LL的初始memset上，比如memset(q,0x3f,sizeof q); 此时，每个数组位置上的值是：4557430888798830399 如果i,j,k三者之间没有关系，就会出现 类似于 g[i,k]+g[k,j]+d[i,j]=3* 4557430888798830399的情况，这个值太大，LL也装不下，值为-4774451407313060419,而此时ans等于INF,肯定满足小于条件，就进入了错误的判断逻辑。

解决的办法有两种：

• g[j][k] + g[k][i] < ans - dis[i][j] 以减法避开三个INF相加,两个INF相加是OK的，不会爆INT
• 将运算前的dis[i][j]转为LL,这样，三个INF不会爆LL