题目描述

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

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

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

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

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

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

1≤N≤100,
1≤M≤10000,
1≤l<500

样例

输入样例：

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

输出样例：

1 3 5 2

题意：一张无向图，输出一个环，这个环上最少三个点，并且这个环是这张图所有存在的环中边权和最小的

题目给出的所有边权值都是>1的，所以在任意一个最小环中都不会有重复的边，否则一定不是最小环

用g数组存储邻接矩阵，用d数组存储做Floyd算法的距离
根据floyd的原理，在进入第k层循环时，d[i][j]仍然是第k-1层的值，也就是说从i到j只经过了1~k-1中的点，那么如果i和k，k和j直接连有路径，那么就找到了一个环，并且g[i][k]和g[k][j]的值是固定的，那么只要d[i][j]最小即可。并且每次更新的时候都有d[i][j]=d[i][k]+d[k][j],并且k是从i到j经过的节点的最大值，所以将这个点记录下来，再向前递归就可以找到路径。并且d[i][k]和d[k][j]中所记录的节点一定不会是k，因为这是上一轮循环的值，节点最大也只到k-1。

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N=110,INF=0x3f3f3f3f;

int g[N][N],d[N][N];
int n,m,cnt;
int path[N];
int node[N][N];

void get_path(int s,int e){
    if(!node[s][e]) return;
    int k=node[s][e];
    get_path(s,k);
    path[cnt++]=k;
    get_path(k,e);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)    g[i][j]=0;
            else    g[i][j]=INF;
        }
    }
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(c,g[a][b]);
    }

    int ans=INF;
    memcpy(d,g,sizeof d);
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if((long long )d[i][j]+g[i][k]+g[k][j]<ans){
                    ans=d[i][j]+g[i][k]+g[k][j];
                    cnt=0;
                    path[cnt++]=k;//要注意顺序，从k开始，i，i->j，j
                    path[cnt++]=i;
                    get_path(i,j);
                    path[cnt++]=j;
                }
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][j]>d[i][k]+d[k][j]){
                    node[i][j]=k;
                    d[i][j]=d[i][k]+d[k][j];
                }
            }
        }
    }
    if(!cnt)    cout<<"No solution.";
    else{
        for(int i=0;i<cnt;i++)  cout<<path[i]<<" ";
    }
    return 0;
}