写在前面

在做洛谷的树上dp题单的时候遇到了一道题目P1613 跑路发现自己对flyod的理解太浅薄了，于是去重新学习了一遍，又做了几道题目，然后结合了acwing的算法提高课的总结，于是乎有了这篇博客。

要说floyd就不能只说板子

什么是floyd，提到floyd肯定就会想到最短路。

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

我们现在看到的形式

for(int k=1;k<=n;k++){
	for(int i=1;i<=n;++j){
		for(int k=1;k<=n;++k){
			d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		}
	}
}

现在我们的板子中经常看到的floyd都是二维，其实最原始的状态是三维。

状态

\(d[k][i][j]\):从\(i\)点到\(j\)点只经过，前k个结点\(（1、2、3、...、k-1、k）\)的最短距离

转移

转移的时候是以经不经过第\(k\)个结点来划分进行转移的。
不经过：
\(d[k][i][j]=d[k-1][i][j]\)
经过：
\(d[k][i][j]=d[k-1][i][k]+d[k-1][j][k]\)
所以状态转移方程为：
\(d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][j][k])\)

空间优化

观察上面的状态转移方程可以看到在算第\(k\)层的状态时，只用到了\(k-1\)层的状态，这就启发了我们是不是可以像背包问题那样，优化掉一维的空间。
我们可以看一下去掉第一维会不会得到的方程是否和原方程等价.
也就是说我们在去点第一维后,在算第\(k\)层的d[i][j]时\(d[i][k]\)和\(d[j][k]\)中存的仍然是第\(k-1\)层的结果.
是不是这样呢?
要想看\(d[i][k]\)和\(d[j][k]\)中存的是不是第\(k-1\)层的结果.我们可以考虑\(d[i][k]\)和\(d[j][k]\)在k层时什么时候会更新
先考虑\(d[i][k]\)什么时候更新

当\(j=k\)时显然第\(k-1\)层的\(d[i][k]\)会更新,我们把\(j=k\)带入有=d[k-1][i][k]

由于\(d[k-1][k][k]=0\),有

所以这是等价变形的.
然后可以考虑\(i=k\)时,情况是一样的.
然后我们就可以证明这两个状态转移方程是等价的.也就有了新的状态转移方程

kij or ijk

从dp的角度考虑也就很自然的会得出循环k在在最外层.
具体的为什么在最外层知乎上已经很多回答了.可以看下面的链接
为什么是kij不是ijk

应用

求多源最短路

AcWing 1125. 牛的旅行

题意是给了一堆牧场

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>


using namespace std;

int n,m;
const int N=200;
const db inf=1e20;
db d[N][N],mv[N];
pdd a[N];
char g[N][N];

void solve() {
	cin>>n;
	rep(i,1,n) {
		cin>>a[i].x>>a[i].y;
	}
	rep(i,1,n) {
		cin>>g[i]+1;
	}


	auto dist=[&](pdd a, pdd b) {
		db dx=a.x-b.x;
		db dy=a.y-b.y;
		return sqrt(dx*dx+dy*dy);
	};

	rep(i,1,n) {
		rep(j,1,n) {
			if(i==j) {
				d[i][j]=0;
			} else if(g[i][j]=='1') {
				d[i][j]=dist(a[i],a[j]);
			} else {
				d[i][j]=inf;
			}
		}
	}

	//跑一遍floyd
	rep(k,1,n) {
		rep(i,1,n) {
			rep(j,1,n) {
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}

	//预处理出来每个点到连通块其他点的最短路的最大值
	db ans1=0,ans2=inf;

	rep(i,1,n) {
		rep(j,1,n) {
			if(d[i][j]<inf) {
				mv[i]=max(mv[i],d[i][j]);
			}
		}
		ans1=max(ans1,mv[i]);
	}
//	cout<<ans2<<endl;

	rep(i,1,n) {
		rep(j,1,n) {
			if(d[i][j]>=inf) {
				ans2=min(ans2,mv[i]+mv[j]+dist(a[i],a[j]));
			}
		}
	}
	cout<<setiosflags(ios::fixed)<<setiosflags(ios::right)<<setprecision(6)<<max(ans1,ans2)<<endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

未完