观光之旅

题目描述：

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

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

思路：

我们先学一下怎么求最小环的值

方法是使用floyed，先回顾一下floyed算法的思想是什么：

dp[k][i][j]表示的是从i到j的路径中只经过节点编号小于等于k的路径的最小值

状态转移方程是：dp[k][i][j] = min(dp[k][i][j], dp[k-1][i][k]+dp[k-1][k][j]);，也就是把i和j的路径分成能包含节点k的和不能包含节点k的这两部分

这里是可以压缩掉第一维度的：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

而求最小环的方法是在跑floyed的基础上，枚举每个k作为最小环上的最大节点，来进一步求最小值的

因为要求最小三个节点，所以我们要保证i, j, k各不相同，也就是在枚举到k的时候，我们要再更新最小值之前去求k作为最小环上最大节点时能产生的最小环的值，而且枚举的时候要保证i!=j

因为我们已经使用1到k-1的点求出i->j的最短路，则要形成k为最大节点的环，就需要i->k和k->j这两条边连接起来形成一个环，也就是dis[i][j] + g[i][k] + g[k][j]，g是图

for(int k = 1; k <= n; ++k){
    for(int i = 1; i < k; ++i){
        for(int j = i + 1; j < k; ++j){
            ans = min(ans, tr[i][k] + tr[k][j] + dis[i][j]);//更新最小环
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);//更新最小值
        }
    }
}

但是这个题求的不是最小值，而是最小环的路径！

因为我们不能清楚的知道求最小值的时候到底取的是哪条边，但是我们可以知道更新dis[i][j]时用的是哪个k，所以开一个pos[i][j]再更新最短路的时候来记录更新i, j时的k，然后求路径的时候就可以递归求i->j之间的路径，

void dfs(int l, int r){
if(pos[l][r] == 0)return;//无节点更新就说明是直接连边
int k = pos[l][r];//找到中间节点
dfs(l, k);//先更新左边
path[++tot] = k;
dfs(k, r);//再更新右边
}

每次有更小的最小环的时候都要重新搞一遍路径

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tr[105][105];
int dis[105][105];
int pos[105][105];
int tot;
int path[200];
int ans;

void dfs(int l, int r){
    if(pos[l][r] == 0)return;
    int k = pos[l][r];
    dfs(l, k);
    path[++tot] = k;
    dfs(k, r);
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            dis[i][j] = tr[i][j] = (i == j ? 0 : (int)1e8);
        }
    }
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        tr[a][b] = tr[b][a] = min(tr[a][b], c);
        dis[a][b] = dis[b][a] = tr[a][b];
    }
    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(ans > tr[i][k] + tr[k][j] + dis[i][j]){
                    ans = min(ans, tr[i][k] + tr[k][j] + dis[i][j]);
                    tot = 0;
                    path[++tot] = k;
                    path[++tot] = i;
                    dfs(i, j);
                    path[++tot] = j;
                }
            }
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(dis[i][j] > dis[i][k] + dis[k][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                    pos[i][j] = pos[j][i] = k;
                }
            }
        }
    }
    if(ans >= 1e8)cout << "No solution.\n";
    else{
        for(int i = 1; i <= tot; ++i)cout << path[i] << ' ';
        cout << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}