Floyd(求最小环+路径) - Sightseeing trip - POJ 1734

Floyd(求最小环) - Sightseeing trip - POJ 1734

题意：

给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式

第一行包含两个整数N和M，表示无向图有N个点，M条边。

接下来M行，每行包含三个整数u，v，l，表示点u和点v之间有一条边，边长为l。

输出格式

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出’No solution.’。

数据范围

$1\le N\le 100,1\le M\le 10000,1\le l<500$

Sample Input：

5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20

Sample Output：

1 3 5 2

---

分析：

$要求至少包含3个点的环，我们假设环i->k->j->...->i。$

$我们知道，floyd算法每次计算i和j之间，经过k的最短距离。$

$在第k层循环时，d[i][j]表示从i到j，经过的点的编号不超过k-1，的最短距离。$

$此时前k-1号点，任意两点之间的最短距离已计算出。$

$则环的最小长度为g[i][k]+g[k][j]+d[j][i]，其中1<i,j＜k，这保证了环上无重复点。$

$用res更新g[i][k]+g[k][j]+d[j][i]的最小值，每更新一次都要重新更新一次具体路径。$

求具体路径：

$对于中间点k，由于从i到k和从k到j的最短路是相互独立的。$

$对于从j到i的最短路：$

$我们可以在更新最短路时，用pos[i][j]=k，来记录最短路上的中间点k，$

$接着递归求从j到k的最短路经过的点，然后把k加入到路径中，再递归求从k到i的最短路经过的点。$

注意：

$计算环的长度可能会爆int。$

代码：

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=110, inf=0x3f3f3f3f; int n,m; int g[N][N],d[N][N]; int pos[N][N]; int path[N],cnt; int res=inf; void get_path(int a,int b) //求从a到b的最短路经过的中间点 { if(pos[a][b]==0) return; int k=pos[a][b]; get_path(a,k); path[cnt++]=k; get_path(k,b); } void floyd() { memcpy(d,g,sizeof g); for(int k=1;k<=n;k++) { for(int i=1;i<k;i++) for(int j=i+1;j<k;j++) //i跟j不能重合 if((long long)g[i][k]+g[k][j]+d[j][i]<res) { res=g[i][k]+g[k][j]+d[j][i]; cnt=0; path[cnt++]=k; //从k到i path[cnt++]=i; get_path(i,j); //从i到j path[cnt++]=j; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; pos[i][j]=k; } } } int main() { cin>>n>>m; memset(g,0x3f,sizeof g); for(int i=1;i<=n;i++) g[i][i]=0; int a,b,c; while(m--) { cin>>a>>b>>c; g[a][b]=g[b][a]=min(g[a][b],c); } floyd(); if(res==inf) puts("No solution."); else for(int i=0;i<cnt;i++) cout<<path[i]<<' '; return 0; }