题解：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)

。代码：

CPP

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}

代码：

CPP

#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;
}

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

文章操作

Floyd 算法

相关推荐

评论

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