题解：P6175 无向图的最小环问题

· · 题解

注意到数据范围 n\le100，所以考虑使用 Floyd 算法解决。

Floyd 算法

这是一种基于 DP 用于求解图上任意两点间最短路的算法。设 f_{k,i,j} 为除 i,j 只经过 1\sim k 的点 i\to j 的最短路，初值设为图的邻接矩阵，则有状态转移方程：

f_{k,i,j}=\min(f_{k-1,i,j},f_{k-1,i,k}+f_{k-1,k,j})

实际实现时可以滚动数组优化掉第一维，时间复杂度 O(n^3)，空间复杂度 O(n^2)。代码：

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

那么我们如何利用 Floyd 求解最小环呢？

在算法中第一层循环枚举到 k 时，可以让 k 为环上的点，并枚举不超过 k 的节点 i,j，那么 i\to k\to j\to\dots\to i 就是经过 i,j,k 的最小环（其中 j\to\dots\to i 为 j\to i 的最短路）。所以答案即为：

\min_{k=1}^{n}\min_{i=1}^{k-1}\min_{j=i+1}^{k-1}f_{k,i,j}+g_{i,k}+g_{k,j}

代码：

#define ll long long
const int _mxn=1000+5;
int n,m;
ll g[_mxn][_mxn],dis[_mxn][_mxn],ans=1e18;
int main()
{
    ___();
    cin>>n>>m;
    memset(dis,0x1f,sizeof(dis));//不能设 0x3f，因为 0x3f3f3f3f3f3f3f3f*3 会爆 long long
    memset(g,0x1f,sizeof(g));
    for(int i=1;i<=n;i++)
        g[i][i]=dis[i][i]=0;
    while(m--)
    {
        int u,v;
        ll w;
        cin>>u>>v>>w;
        w=min(w,g[u][v]);//要判重边
        g[u][v]=g[v][u]=dis[u][v]=dis[v][u]=w;
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                ans=min(ans,dis[i][j]+g[i][k]+g[k][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    ans==1e18?cout<<"No solution."<<endl:cout<<ans<<endl;
    return 0;
}