poj1734 Sightseeing trip(图论/floyd无向图代价最小环+输出路径)

题目

n(n<=100)个点，m(m<=1e4)条边的无向图，

第i条边的代价为ci(0<=ci<=500)，无自环，可能有重边，

要求输出最小环上的点，若有多解，输出一解即可

思路来源

https://www.cnblogs.com/TengXunGuanFangBlog/archive/2013/04/19/loop_problem.html

题解

pre[i][j]代表在i到j的最短路中j的前驱，

则pre[i][j]=pre[i][k]+pre[k][j]发生更新时，i-->j由i-->k和k-->j更新而来，

此时前驱一定是pre[k][j]，即令pre[i][j]=pre[k][j]即可，

最小环代价发生更新时，暴力更新路径，这里均摊的复杂度不太懂啊orz

代码

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=105,INF=1e7; 
int n,m,u,v,w,dp[N][N],mp[N][N],pre[N][N];
vector<int>res;
bool upd(int &x,int y)
{
	if(x>y)
	{
		x=y;
		return 1;
	}
	return 0;
} 
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;++i)
		{
			for(int j=i+1;j<=n;++j)
			{
				mp[i][j]=mp[j][i]=INF;
				dp[i][j]=dp[j][i]=mp[i][j];
				pre[i][j]=i;pre[j][i]=j;
			}
		}
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d%d",&u,&v,&w);
			mp[u][v]=mp[v][u]=min(mp[u][v],w);
			dp[u][v]=dp[v][u]=mp[u][v];
		}
		int ans=INF;
		for(int k=1;k<=n;++k)
		{
			for(int i=1;i<k;++i)
			{
				for(int j=i+1;j<k;++j)
				{
					if(upd(ans,mp[k][i]+dp[i][j]+mp[j][k]))
					{
						res.clear();
						for(int x=j;x!=i;x=pre[i][x])
							res.push_back(x);
						res.push_back(i);
						res.push_back(k);
					}
				}
			}
			for(int i=1;i<=n;++i)
			{
				for(int j=1;j<=n;++j)
				{
					if(upd(dp[i][j],dp[i][k]+dp[k][j]))
					{
						pre[i][j]=pre[k][j];
					}
				}
			}
		}
		if(ans==INF)
		{
			puts("No solution.");
			continue;
		}
		else 
		{
			int sz=res.size();
			for(int i=0;i<sz;++i)
				printf("%d%c",res[i]," \n"[i==sz-1]);
		}
	}
	return 0;
}