胡扯扩展Floyd算法

Problem

给定一个有向图，求一个至少经过2个点的最小环。

Solution

Floyd算法的代码如下

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

外层循环执行完$k==X$的循环，表示两两节点之间只走$1...X$的最短路已经被求出。 考虑一个环，上面一定有一个编号最大的点 以上图为例，在第66次循环之前，所有点对经过$1...65$的最短路已经求出，由于最短路中一定没有点$66$，所以可以放心地尝试把$66$号点加进去而不必担心出现重边。 于是算法就出来了：额外记录原图的边$edge[][]$，在$sp[][]$上求最短路。第$k$次循环之前，枚举每对点$i,j< k$，把$sp[i][j]$连到$edge[j][k]$和$edge[k][i]$上，用这个环的大小来更新答案。

Code

for(int k=1;k<=n;k++)
{
    for(int i=1;i<k;i++)
        for(int j=i+1;j<k;j++)
            chkmn(res,sp[i][j]+dist[j][k]+dist[k][i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            chkmn(sp[i][j],sp[i][k]+sp[k][j]);
}