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

最小环是什么？

最小环是求一个图中最小的环 （说了和白说一样）

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++)//为了不找到重复的，可以这样循环或者if(i==j)continue;
            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求最短路
  }

如果需要增加路径的画，就可以在 disi=min()的后面加一条

例题

HDU 1599

一道模板题

信息传递

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

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

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