观光之旅

题面：

        原题链接

题意：

        求一张无向图上的最小环。

题解：

        最小环问题：给出一个图，问其中的有 n 个节点构成的边权和最小的环（n≥3）是多大。图的最小环也称围长。最小环问题的解法依照给定的图的类型而定，题目给定的是一张无向图，一般使用 floyd。

        我们知道在 floyd 算法的过程中，在最外层的 k 循环开始时，dis[i][j] 保存着经过编号不超过 k-1 的节点的从 i 节点到 j 节点的最短路长度，所以 min｛ dis[i][j] + a[j][k] + a[k][i] } 是满足

        1、由编号不超过 k 的节点组成

        2、经过编号为 k 的节点

以上两个条件的最小环的长度，同时 i 节点和 j 节点是与 k 相邻的两节点。这样我们对于 k [1,n]，都如此枚举就能得到这张无向图上的最小环。以下给出了部分代码。

        另外，对于有向图的最小环问题，可枚举起点 S[1,n]，执行 堆优化的dijkstra，S 一定是第一个被从堆中取出的节点，我们扫描 S 的所有出边，拓展、更新完后令 dis[S]=INF，然后继续跑 dijkstra，当 S 第二次被取出时，dis[S] 就是经过点 S 的最小环长度。

代码：

il void get(int x,int y)
{
	//i到j的最短路没有经过其他节点,则退出 
	if(!pos[x][y]) return ;
	//否则,i~k~j的话,递归处理i~k的部分和k~j的部分
	get(x,pos[x][y]);
	path.push_back(pos[x][y]);
	get(pos[x][y],y);
}
for(int k=1;k<=n;k++)
{
	//至少包含三个点的环所经过的点的最大编号是k
	for(int i=1;i<k;i++)
	{
		for(int j=i+1;j<k;j++)
		{
			//至少包含三个点,i,j,k不重合
			if(dis[i][j]+a[j][k]+a[k][i]<ans)
			{
				//注意,每当迭代到这的时候
                //d[i][j]存的是上一轮迭代Floyd得出的结果
				ans=dis[i][j]+a[j][k]+a[k][i];
				path.clear();
				get(i,j);//递归求i到j的路径
				path.push_back(j);
				path.push_back(k);
				path.push_back(i);
			} 
		}
	}
	//Floyd,更新一下所有ij经过k的最短路径
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(dis[i][j]>dis[i][k]+dis[k][j])
			{
				dis[i][j]=dis[i][k]+dis[k][j];
				pos[i][j]=k;//pos存的是中间点
			}
		}
	}
}