最小环

又写了一篇博客
嘿嘿~没想到吧?

最小环是什么?

最小环是求一个图中最小的环(说了和白说一样)

Dij求法

每一次除去一条边(u,v)然后再求u到v的最短路径

时间复杂度: $O(m(n+m)log n)$

floyd求法

由于构成一个环至少需要3个点,所以我们设w为最大点,u和v分别是这个环上与它相邻的两个点。

由于三个点能确定一个环,所以这个环的大小为 u和v之间的最短路+u到w的距离+w到v的距离

ans=min(ans,mindis[u][v]+dis[u][w]+dis[w][v]

其他的就按照普通的floyd来求最短路即可。

代码

for (int i=1;i<=n;i++)
    for (int j=1; j<=n;j++)dismin[i][j]=dis[i][j];//init
int ans=2147483647;
for (int k=1;k<=n;k++) {
    for (int i=1;i<k;i++)
        for (int j=1;j<i;j++)
            ans=min(ans,mindis[i][j]+dis[i][k]+dis[k][j]); //计算环的大小并更新答案
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            dis[i][j]=min(mindis[i][j],mindis[i][k]+mindis[k][j]); //floyd求最短路
  }

例题

HDU 1599

一道模板题

信息传递

这道题明显是求最小环,但是用floyd或dij都会超时。

仔细一看。。。发现这道题的图非常特殊,每一个节点指向并只指向一个节点。

所以可以选择用拓扑或并查集做。

本文链接:https://kaispace.com.cn/index.php/archives/531/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者

    jyeric
    jyeric  2019-10-01, 08:57

    拖更可耻(博主nodeee因拖更被打。)(等待。我博客也好像老久没更...)