「POJ1734」Sightseeing trip

题意：给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

考虑 Floyd 算法，$d[i,j]$ 表示经过编号不超过 $k-1$ 的节点，从 $i$ 到 $j$ 的最短路。

所以，以下就是满足这两个条件的最小环长度：

1. 由编号不超过 $k$ 的节点组成；
2. 经过节点 $k$。

$$\min \limits_{1\leq i<j<k}(d[i,j]+a[j,k]+a[k,i])$$

上式中的 $i$ 和 $j$ 相当于枚举了环上与 $k$ 相邻的两个点，所以结论成立。

然后对于 $k\in [1,n]$ ，都算一遍，就可以得到最小环。

我们对每个 $k$ 只考虑了编号不超过 $k$ 的节点构成的最小环，没有考虑编号大于 $k$ 的节点，但是由于对称性，这样并不影响。

注意要用 vector 存储环的路径。

如果是有向图的最小环问题，就枚举起点 $s$，用 Dijkstra 求最短路，$s$ 一定是第一个被取出堆中的节点，扫描 $s$ 的所有出边，扩展完成后令 $dis[s]=+\infty$。如果 $s$ 第二次被堆中取出，$dis[s]$ 就是最小环的长度。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,ans=0x3f3f3f3f;
int pos[110][110];
int a[110][110],dis[110][110];
vector<int> p;
void solve(int i,int j)
{
	if(pos[i][j]==0)
		return ;
	solve(i,pos[i][j]);//pos[i][j]存储i和j中的中间点
	p.push_back(pos[i][j]);
	solve(pos[i][j],j);
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++)
		a[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[u][v]=a[v][u]=min(a[u][v],w);
	}
	memcpy(dis,a,sizeof(a));
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<k;i++)
			for(int j=i+1;j<k;j++)
				if((long long)dis[i][j]+a[j][k]+a[k][i]<ans)
				{
					ans=dis[i][j]+a[j][k]+a[k][i];
					p.clear();
					p.push_back(i);
					solve(i,j);//处理i和j之间的路径
					p.push_back(j);
					p.push_back(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;
				}
	}
	if(ans==0x3f3f3f3f)
		printf("No solution.");
	else
		for(int i=0;i<(int)p.size();i++)
			printf("%d ",p[i]);
	return 0;
}