Floyd求最小权值环问题

Author Avatar
ajcxsu 2018年03月16日
  • 106 次阅读

Problem - BZOJE1698

给定一个无向图,找一个环使得环上的权值相加最小。
环的定义:从一个点出发能沿着一条不重复遍历边的路径回到该点,这个路径为无向图的环。

Solution

使用Floyd求解该问题。 我们每次从小到大枚举中转点k来对每对点之间的路径进行松弛。 那么在枚举中转点k之前,显然已经求出来的最短路图中只能包含$1...k-1$这些点。换而言之,这些最短路不可能包含k。 于是可以枚举与k相连的不同点i,j。则某次求得的最小环的权值为$dist[i][j]+e[i][k]+e[k][j]$。

之后再以k为中转点进行松弛。

Code

// Code by ajcxsu
// Problem: BZOJE P1698

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

const int N=251;
int e[N][N];
int d[N][N];

int main() {
    ios::sync_with_stdio(false);
    memset(e,0x3f,sizeof(e));
    memset(d,0x3f,sizeof(d));
    int n,m;
    cin>>n>>m;
    int u,v,w;
    for(int i=1;i<=m;i++) cin>>u>>v>>w, e[u][v]=e[v][u]=d[u][v]=d[v][u]=w;
    int ans=INF;
    for(int k=1;k<=n;k++) {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++) // 显然i不能等于j,否则会变成d[i][j]==0的情况。由于我没有初始化d[i][j],因此会出来更加奇怪的答案
                if(d[i][j]!=INF && e[i][k]!=INF) ans=min(ans, d[i][j]+e[i][k]+e[k][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
    if(ans!=INF) cout<<ans<<endl;
    else cout<<"He will never come back."<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/floyd_minium_quote.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。