无向图的最小环问题『Floyd』

枚举环中相邻的三点：$i$,$j$,$k$，此时环上边权和最小为$d[i,j]+a[j,k]+a[k,i]$。

$d[i,j]$为$i$~$j$所有不经过$k$的路径中最短的。

观察$Floyd$的特点：在最外层循环为$k$时，$i$~$j$的最短路一定不经过$k$。所以我们在更新以$k$为断点的最短路前先枚举最小环($i<j<k$)。

放代码！

#include<bits/stdc++.h>
using namespace std;
const int N=105,INF=1e8;
int n,m,ANS,a[N][N],d[N][N],pos[N][N];
vector<int>ans;

void get_path(int x,int y) {
    if(!pos[x][y]) return ;
    get_path(x,pos[x][y]);
    ans.push_back(pos[x][y]);
    get_path(pos[x][y],y);
}

int main() {
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    int x,y,z;
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    ANS=INF;
    memcpy(d,a,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]+a[j][k]+a[k][i]<ANS) {
            ANS=d[i][j]+a[j][k]+a[k][i];
            ans.clear();
            ans.push_back(i);
            get_path(i,j);
            ans.push_back(j);
            ans.push_back(k);
          }
        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;
          }
    }
    if(ANS==INF) return puts("No solution."),0;
    for(int i=0;i<ans.size();i++) 
     printf("%d ",ans[i]);
}

无向图的最小环问题『Floyd』

相关推荐