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://pst.iorinn.moe/archives/floyd_minium_quote.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆