目录
Floyd——人人都是中间商
引入
- 有n座相互孤立的岛屿，每座岛屿都拥有被其他岛屿搭建桥梁的机会，但在起始的时候，每座岛屿并没有向其他岛屿搭建桥梁的能力，突然有一天，资金突然丰富起来了，但只能按顺序给这些岛屿，并使得这些岛屿具有向其他岛屿搭建桥梁的机会，同时一旦发现要新搭建的且能使得AB两地的桥梁长度比原本使得AB两地通行的桥梁来得短，就拆掉原本的桥梁，搭起新桥梁，否则就放弃新的搭建计划。
粗糙的原理分析
- Floyd本质上是动态规划，在未做滚动数组优化来省去一个维度时，
dist[k][i][j]表示的是在使用前k个结点时，点i到点j的最短距离，而当k==总结点时即已经纳入了所有的点(所有的情况)进行了考虑。
注意点
初始化
- 起初各自点并没有来当中介的点，只能自己到达自己 （给距离赋值为0），而无法到达别人家（给距离赋值为INF）
赋值
- 可能出现重边的现象（所谓重边就是两个点之间存在两条及以上的边），这个时候我们应该保留较小的边就行。
适用
- 小空间稠密阵
- 能接受$ O(n^3)$的题目。
应用
模板题
AcWing 854. Floyd求最短路
#include<bits/stdc++.h>
using namespace std;
const int N= 2e2+10,INF =0x3f3f3f3f;
int n,m,q;
int dist[N][N];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
int main()
{
memset(dist,0x3f,sizeof(dist));
cin>>n>>m>>q;
for(int i=1;i<=n;i++)dist[i][i]=0;//起初各自点并没有中介的点，只能自己到达自己
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
dist[x][y]=min(dist[x][y],z);//有可能出现重边
}
floyd();
for(int i=0;i<q;i++)
{
int x,y;
cin>>x>>y;
if(dist[x][y]!=INF)
cout<<dist[x][y]<<endl;
else cout<<"impossible"<<endl;
}
return 0;
}
直径的拼凑问题
#include<bits/stdc++.h>
using namespace std;
const int N = 260,INF = 99999999;
int n;
struct dot{
double x,y;
};
char g[N][N];//记录的仅仅是第i个点是否和第j点联通的情况
double dist[N][N];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
double get_dist(dot a,dot b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) dist[i][i]=0;//错误点：不要让后面的操作覆盖掉它
dot dots[n+1];
for(int i=1;i<=n;i++)
cin>>dots[i].x>>dots[i].y;
//读入联通的情况
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
if(g[i][j]=='1')
dist[i][j]=get_dist(dots[i],dots[j]);
else if(i!=j)
dist[i][j]=INF;
}
floyd();
//(间接联通)可以借用dist数组来判断联通关系比较模糊的两点之间的情况
//不用再去写并查集
//要找直径，就是要确立当前点中到所有连接的点中的最远距离
double ans1=0;//答案有可能在自己圈里，新加入的牧场由于长度太小，可能没有对直径产生影响
double max_dot_dis[N+1];
memset(max_dot_dis,0,sizeof(max_dot_dis));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(dist[i][j]!=INF)
{
max_dot_dis[i]=max( max_dot_dis[i], dist[i][j] ); // cout<<max_dot_dis[i]<<" ";
ans1=max( ans1, max_dot_dis[i] );
}
}
}
double ans2=INF;//比小要设大，比大要设小
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dist[i][j]==INF)//如果两者距离比较大(没有联通而已，但还是有距离)，则认为两者分属不同的牧场
ans2=min( max_dot_dis[i] + max_dot_dis[j] + get_dist(dots[i],dots[j]) ,ans2);//错误点2：取小
cout<<fixed<<setprecision(6)<<max(ans1,ans2);//这里是*取其大，两小中取较大者
return 0;
}
无向图的最小环问题