首页 > 代码库 > Floyd求最小环
Floyd求最小环
首先求最小环有一个比较好想的方法：每次删掉一条边，看看这条边n所连的点i之间的距离（dijkstra），时间复杂度O(m*V^2*logv)
其实floyd也能完成这个功能。f[i][j][k]表示i到j在中间点为1~k的最近距离
对于一个环，我们假设i和j中只夹这一个数k，则环长为f[i][j][k-1]+map[i][k]+map[k][j],枚举一下
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define rep(i,a,b) for(int i=a;i<=b;++i)using namespace std;int n,map[1005][1005],dist[1005][1005],Min;void have_done(){ rep(k,1,n) { rep(i,1,k-1) { rep(j,1,k-1) { if(map[i][k]+map[k][j]+dist[i][j]<Min) { Min=map[i][k]+map[k][j]+dist[i][j]; } dist[i][j]=min(dist[i][j],map[i][k]+map[k][j]); } } }}int main(){ Min=100000; scanf("%d",&n); rep(i,1,n) rep(j,1,n) { scanf("%d",&map[i][j]); } have_done(); cout<<Min<<endl;}
Floyd求最小环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。