求最小环算法介绍

无向图的最小环

代码实现

#include<iostream>
#include<cstring>
using namespace std;
const int N=105,M=10005,INF=0x3f3f3f3f;
int n,m;
int d[N][N],w[N][N];
int pos[N][N];//记录当前状态由哪个点转移过来
int path[N],cnt;//

void get_path(int i,int j)//i->j之间不包含ij的路
{
    if(pos[i][j]==0)return;//说明ij之间不经过其它点
    int k=pos[i][j];
    get_path(i,k);
    path[cnt++]=k;
    get_path(k,j);
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(w,0x3f,sizeof w);
    for(int i=1;i<=n;i++)w[i][i]=0;
    for(int i=0;i<m;i++)
    {
        int u,v,l;
        scanf("%d%d%d",&u,&v,&l);
        w[u][v]=w[v][u]=min(w[u][v],l);
    }

    int ans=INF;//最小环的长度
    memcpy(d,w,sizeof d);
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)//此时的d[i][j]为未迭代至k的最短路，故一定不包含k
            for(int j=i+1;j<k;j++)//可以保证该通路为环
            if( (long long)d[i][j]+w[i][k]+w[k][j]<ans)
            {
                ans=d[i][j]+w[i][k]+w[k][j];
                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][j]>d[i][k]+d[k][j])
        {
            d[i][j]=d[i][k]+d[k][j];
            pos[i][j]=k;//记录路径上前一个顶点
        }
    }
    if(ans==INF)puts("No solution.");
    else
    {
        for(int i=0;i<cnt;i++)printf("%d ",path[i]);
        cout<<endl;
    }
    return 0;
}