题目描述:

给定一张无向图，求图中一个至少包含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

Floyd

1.本题的思路就是考虑最小环里面节点编号最大的节点为k,且环里面与k相连的两个点为i，j，环的长度为g[i][k]+g[k][j]+d[j][i];🐱‍🏍

2.则d[j][i]则表示j到i且经过的节点编号小于k,因为在环中k就是最大的👍，只能经过小于k的节点了;

3.则这与floyd中k次循环开始前的d[i][j]意义相同;

4.那就不妨在floyd的第一重循环就求一下以k为最大节点编号的环的长度，美滋滋😁，注意这里的k必须与节点的意义一样：0-n-1或1-n;

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int n,m;
int d[N][N],g[N][N];
int pos[N][N];
int path[N],cnt;
void get_path(int i,int j)
{
    if(pos[i][j]==0) return;//表示pos没有被更新过，即i,j间直达不需要借助节点就最短；
    int temp=pos[i][j];//即i,j间借助的节点的编号最大的那个，也是小于k的
    get_path(i,temp);
    path[cnt++]=temp;
    get_path(temp,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;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    memcpy(d,g,sizeof(g));//注意拷贝
    int res=INF;//答案
    for(int k=1;k<=n;k++)//每一次开始本次floyd时，d[i][j]的实际意义是从i到j经过的节点编号最大就是k-1
    {
        for(int i=1;i<k;i++)//注意i和j的枚举范围
        {
            for(int j=i+1;j<k;j++)
            if(g[i][k]<INF/2&&g[k][j]<INF/2&&g[i][k]+g[k][j]+d[j][i]<res)//不加前两个判断会爆int
            {
                res=g[i][k]+g[k][j]+d[j][i];
                //记录最小环
                cnt=0;
                path[cnt++]=k;
                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][k]+d[k][j]<d[i][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    pos[i][j]=k;//代表i到j的最短距离要紧过节点编号不超过k的若干点，且一定经过k点
                }
            }
        }
    }
    if(res==INF) puts("No solution.");
    else
    {
        for(int i=0;i<cnt;i++)
        cout<<path[i]<<" ";
        cout<<endl;
    }
    return 0;
}

给个收藏吧，谢谢阅读💛💛💛💛