Floyd求最小环!(转载,非原创) 附加习题(原创。)HDU-1599

//Floyd 的 改进写法可以解决最小环问题,时间复杂度依然是 O(n^3),储存结构也是邻接矩阵

int mincircle = infinity;
Dist = Graph; for(int k=;k<nVertex;++k){
//新增部分:
for(int i=;i<k;++i)
for(int j=;j<i;++j)
mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);
//通常的 floyd 部分:
for(int i=;i<nVertex;++i)
for(int j=;j<i;++j){
int temp = Dist[i][k] + Disk[k][j];
if(temp < Dist[i][j])
Dist[i][j] = Dist[j][i] = temp;
}
}

以上为网上流传的Floyd求最小环的主代码。我们发现,最下面两重循环就是Floyd原来的代码,新增的就是上面那个判环部分。一开始,我不明白,为什么要把新增的放在前面,两者的顺序能不能调换?现在的理解是这样的:在第k层循环,我们要找的是最大结点为k的环,而此时Dist数组存放的是k-1层循环结束时的经过k-1结点的最短路径,也就是说以上求出的最短路是不经过k点的,这就刚好符合我们的要求。为什么呢?假设环中结点i,j是与k直接相连,如果先求出经过k的最短路,那么会有这样一种情况,即:i到j的最短路经过k。这样的话就形成不了环,显然是错误的。当时还有一个问题,就是为什么要多开一个Dist数组呢,一个Graph不是足够了吗?其实好好想想,出现的问题和前面是一个道理。如果只开Graph,那么它里面的值就会不断改变,也会存在路径覆盖的情况,导致形成不了环或不是最小环。举个例子:假设现在进行第k层循环,i,j为枚举出来与k直接相连的边。由于此时Graph是动态的,原来根本不存在i到k的一条边,现在可能经过其它结点形成了“边”,但它未必是与k直接相连的边。以上两个问题花了我半天时间来弄懂,由于网上也没有找到关于这些问题的(可能我比较笨吧),所以要写这些东西,但又写得挺乱……

题目大意:中文题,求三个地点形成的最小环。

解决方法:之上的floyd最小环算法;

AC代码:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
int n,m;
int map_[][];
int dis[][];
int main()
{
while (cin>>n>>m)
{
memset(map_,INF,sizeof(map_));
for (int i=; i<=m; i++)
{
int a,b,c;
cin>>a>>b>>c;
//cout<<a<<b<<c<<endl;
map_[a][b]=map_[b][a]=min(c,map_[a][b]);
// cout<<map_[a][b]<<map_[b][a]<<endl;
}
for (int i=; i<=n; i++)
{
for (int j=; j<=n; j++)
{
// cout<<map_[i][j]<<" ";
dis[i][j]=map_[i][j];
}//cout<<endl;;
}
int ans=INF;
for (int k=; k<=n; k++)
{
for (int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if (i!=j&&j!=k&&i!=k&&map_[i][k]!=INF&&map_[k][j]!=INF&&dis[i][j]!=INF)
{
ans=min(ans,dis[i][j]+map_[j][k]+map_[k][i]);
//cout<<ans<<endl;
}
}
}
for (int i=; i<=n; i++)
{
for (int j=; j<=n; j++)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
if (ans==INF) cout<<"It's impossible."<<endl;
else
cout<<ans<<endl;
}
return ;
}
上一篇:C#.NET 大型企业信息化系统集成快速开发平台 4.2 版本 - 适合大型企业信息化应用使用的角色权限管理体系


下一篇:Xcode清除缓存、清理多余证书