题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1599
最小环的定义：经过一条简单路径（除起点每点只经过一次）回到起点成为环，并且环的总长度最小称为最小环。
关于floyd算法路径的计算方式参考博客：http://blog.sina.com.cn/s/blog_6fbae1120100xfdd.html
floyd算法很好的运用了dp的思想，dp是一个多阶段优化问题，因为最短路最多经过n-1个其他结点，所以最多迭代n次求出最终结果。我们用dp[m][i][j]表示前m个阶段的计算时（i,j）之间的最短距离，所以有dp[m][i][j]=min(dp[m-1][i][k]+dp[m-1][k][j])也就是用前m-1个阶段的（i,k）(k,j)之间的最短距离更新第m个阶段的（i,j）之间的最短距离，这个迭代过程最多是n次，因为第m次迭代会使得（i,j）之间经过k=0,1,2,m-1的距离更新成当前最小。可以滚动优化这个dp方程为dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])，外层叠加n层迭代即可。
对于至少三个点的最小环，我们可以枚举最大的点k，在floyd更新的过程中以1,2....k-1为中转点的d[i][j]已经更新完毕，此时只要枚举比k小的i和j，其中i是k之前的一个结点，j是k之后的一个结点，且i不等于k，再加上d[i][j]就是以k为最大点，（i,k）&（k,j）为两条边的环的大小，通过两层（i,j）循环就能得出以k为最大点的环的最小值，在套一层k循环便能得出整个图的最小环。打印路径也是可以做到的，可以定义nxt[i][j]是从i到j的当前路径的i的下一个结点，所以只要在d[i][j]<d[i][k]+d[k][j]更新成功的时候对更新nxt[i][j]=nxt[i][k]就可以了，因为nxt[k][j]在之前已经更新过了.
这道题有一个注意点，就是inf的设置，我设置inf为0x7f7f7f7f时炸了，一看原来是对Map设置了inf的时候，floyd里面套了两个Map，所以越界了，所以最好inf设置合适点，比如0x7ffffff。
裸hdu1599代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch==‘-‘)w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-‘0‘,ch=getchar(); 25 return ans*w; 26 } 27 const int maxn=105; 28 int n,m,t; 29 int dis[maxn][maxn],Map[maxn][maxn]; 30 int ans; 31 int cnt; 32 void floyd() 33 { 34 f(k,1,n) 35 { 36 f(i,1,k-1) 37 f(j,i+1,k-1) 38 { 39 int tmp=dis[i][j]+Map[i][k]+Map[k][j];//注意inf两倍不能超过int范围orz 40 if(tmp<ans)ans=tmp; 41 } 42 f(i,1,n) 43 f(j,1,n) 44 { 45 if(dis[i][j]>dis[i][k]+dis[k][j]) 46 { 47 dis[i][j]=dis[i][k]+dis[k][j]; 48 } 49 } 50 } 51 } 52 int main() 53 { 54 //freopen("input.txt","r",stdin); 55 //freopen("output.txt","w",stdout); 56 std::ios::sync_with_stdio(false); 57 while(scanf("%d%d",&n,&m)!=EOF) 58 { 59 int u,v,w; 60 f(i,0,maxn-1) 61 f(j,0,maxn-1)dis[i][j]=Map[i][j]=inf; 62 ans=inf; 63 while(m--) 64 { 65 u=read(),v=read(),w=read(); 66 if(Map[u][v]>w) 67 { 68 Map[u][v]=Map[v][u]=dis[u][v]=dis[v][u]=w; 69 } 70 } 71 floyd(); 72 if(ans==inf)pf("It‘s impossible.\n"); 73 else 74 pf("%d\n",ans); 75 } 76 return 0; 77 }
输出最小环路径的代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch==‘-‘)w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-‘0‘,ch=getchar(); 25 return ans*w; 26 } 27 const int maxn=105; 28 int n,m,t; 29 int dis[maxn][maxn],Map[maxn][maxn],path[maxn],nxt[maxn][maxn]; 30 int ans; 31 int cnt; 32 void floyd() 33 { 34 f(k,1,n) 35 { 36 f(i,1,k-1) 37 f(j,i+1,k-1) 38 { 39 int tmp=dis[i][j]+Map[i][k]+Map[k][j];//注意inf两倍不能超过int范围orz 40 if(tmp<ans) 41 { 42 ans=tmp; 43 cnt=0; 44 int p=i; 45 while(p!=j)//最小环的路径 46 { 47 path[cnt++]=p; 48 p=nxt[p][j]; 49 } 50 path[cnt++]=j; 51 path[cnt++]=k; 52 } 53 } 54 f(i,1,n) 55 f(j,1,n) 56 { 57 if(dis[i][j]>dis[i][k]+dis[k][j]) 58 { 59 dis[i][j]=dis[i][k]+dis[k][j]; 60 nxt[i][j]=nxt[i][k]; 61 } 62 } 63 } 64 } 65 int main() 66 { 67 //freopen("input.txt","r",stdin); 68 //freopen("output.txt","w",stdout); 69 std::ios::sync_with_stdio(false); 70 while(scanf("%d%d",&n,&m)!=EOF) 71 { 72 int u,v,w; 73 f(i,0,maxn-1) 74 f(j,0,maxn-1)dis[i][j]=Map[i][j]=inf,nxt[i][j]=j; 75 ans=inf; 76 while(m--) 77 { 78 u=read(),v=read(),w=read(); 79 if(Map[u][v]>w) 80 { 81 Map[u][v]=Map[v][u]=dis[u][v]=dis[v][u]=w; 82 } 83 } 84 floyd(); 85 if(ans==inf)pf("It‘s impossible.\n"); 86 else 87 { 88 pf("%d\n",ans); 89 f(i,0,cnt-1)pf("%d ",path[i]); 90 pf("\n"); 91 } 92 } 93 return 0; 94 }
hdu1599 图的最小环问题的floyd算法+path输出
原文：https://www.cnblogs.com/randy-lo/p/12589958.html