floyd总结 - 洛谷保存站

# floyd
## Part1
### 1. 算法介绍
Floyd 算法是一种用于解决**所有顶点对之间最短路径问题**的算法。可用于计算任意两点的最短路径及长度。时间复杂度为 $O(n^3)$ 。

### 2.核心思想

- 通过一个二维数组  $d[ ][  ]$  来记录最短路径及长度。
- 通过三层for循环枚举 $k,i,j$ ,考虑以 $k$ 为中转点时，点 $i$ 到 $j$ 的最短路径。
- 转移方程：
```cpp
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
```
> 
> $min(d[i][j],d[i][k]+d[k][j])$ 
>
其中  $d[i][j]$  表示不经过点 $k$ 直接从 $i$ 到 $j$ 的路径长度， $d[i][k]+d[k][j]$  则表示经过点 $k$ 中转的路径长度，最终取最小值。
### 3.模板
- 通过邻接矩阵存储图
- 初始化：开始时 $d$ 数组设为无穷大（如果 
 $i$  和  $j$  之间没有直接的边，则应为 无穷大）,点 $d[i][i]=0$ （一个点到自身的距离为0）
- 三重 $for$ 循环遍历，记录所有点之间的最短路

代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,d[1001][1001];//设有n个点，m条路径。
int main(){
	for(int i=1;i<=1000;i++){
		for(int j=1;j<=1000;j++){
			d[i][j]=1e9;//初始化
		}
	}
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		d[i][i]=0; //初始化
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		d[u][v]=w;
		d[v][u]=w; //建边，此处建的是双向边；
	}
	for(int k=1;k<=n;k++){ //枚举中转点
		for(int i=1;i<=n;i++){ //枚举起点
			for(int j=1;j<=n;j++){ //枚举终点
				d[i][j]=min(d[i][k]+d[k][j],d[i][j]); //公式
			}
		}
	}
	int x,y;
	cin>>x>>y;
	cout<<d[x][y]<<endl;
	return 0;
}
```
## Part2
### B3647
[B3647 【模板】Floyd](https://www.luogu.com.cn/problem/B3647)

本题是模板，直接按Floyd思路写就行，注意有重边。

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,d[1001][1001];
int main(){
	for(int i=1;i<=1000;i++){
		for(int j=1;j<=1000;j++){
			d[i][j]=100000000;
		}
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		d[u][v]=min(d[u][v],w);
		d[v][u]=min(d[v][u],w);
	}
  for(int i=1;i<=n;i++){
		d[i][i]=0;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(d[i][j]>d[k][j]+d[i][k]){
					d[i][j]=d[k][j]+d[i][k];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<d[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}
```
### P3884
[P3884 [JLOI2009] 二叉树问题](https://www.luogu.com.cn/problem/P3884)

本题中：
- 深度：点 $i$ 的深度就是 $d[i][j]$ 的值。 
- 宽度：可在跑Floyd时用一个桶 $deep$ 记录相同深度的点的数量，取最大值即可。
-  $x,y$ 的距离 ：因为题目中
> 保证  $u$  是  $v$  的父结点

所以在建边时把 $d[v][u]$ 计为 $2$ 即可。

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,deep[100001],d[1001][1001];
int main(){
	for(int i=1;i<=1000;i++){
		for(int j=1;j<=1000;j++){
			d[i][j]=100000000;
		}
	}
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		d[u][v]=1;
		d[v][u]=2;
	}
	for(int i=1;i<=n;i++){
		d[i][i]=0;
	}
	int x,y;
	cin>>x>>y;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
				}
			}
		}
	}
	int ansd=0,answ=0;
	for(int i=1;i<=n;i++){
		deep[d[1][i]]++;
		ansd=max(ansd,d[1][i]);
	}
	for(int i=1;i<=n;i++){
		answ=max(answ,deep[i]);
	}
	cout<<ansd+1<<endl;
	cout<<answ<<endl;
	cout<<d[x][y];
	return 0;
}
```
### P1364
[P1364 医院设置](https://www.luogu.com.cn/problem/P1364)

跑一遍Floyd,再枚举每个点作为医院，求最小值即可
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,d[1001][1001],r[1001];
int main(){
	cin>>n;
	for(int i=1;i<=1000;i++){
		for(int j=1;j<=1000;j++){
			d[i][j]=100000000;
		}
	}
	for(int i=1;i<=n;i++){
		d[i][i]=0;
	}
	for(int i=1;i<=n;i++){
		int u,v,w;
		cin>>w>>u>>v;
		r[i]=w;
		if(u!=0){
			d[i][u]=1;
			d[u][i]=1;	
		}
		if(v!=0){
			d[i][v]=1;
			d[v][i]=1;
		}
	}
	for(int k=1;k<=n;k++){
		for(int j=1;j<=n;j++){
			for(int i=1;i<=n;i++){
				if(d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
				}
			}
		}
	}
	ll ans=1000000008;
	ll sum=0;
	for(int i=1;i<=n;i++){
		sum=0;
		for(int j=1;j<=n;j++){
			sum+=d[j][i]*r[j];
		}                                                                          
		ans=min(sum,ans);
	}
	cout<<ans;
	return 0;
}
```
### P1828
[P1828 [USACO3.2] 香甜的黄油 Sweet Butter](https://www.luogu.com.cn/problem/P1828)

与医院设置类似，但有几个坑点：
1. 有 $n,p,c$ 三个变量， $for$ 循环遍历时容易混淆。
2. 数据较大，要开 long long。

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,p,c,d[1001][1001],mc[100900];
int main(){
	cin>>n>>p>>c;
	for(int i=1;i<=p;i++){
		for(int j=1;j<=p;j++){
			d[i][j]=1e9;
		}
	}
	for(int i=1;i<=p;i++){
		d[i][i]=0;
	}
	for(int i=1;i<=n;i++){
		cin>>mc[i];
	}
	for(int i=1;i<=c;i++){
		int a,b,D;
		cin>>a>>b>>D;
		d[a][b]=min(d[a][b],D);
		d[b][a]=min(d[b][a],D);
	}
	for(int k=1;k<=p;k++){
		for(int i=1;i<=p;i++){
			for(int j=1;j<=p;j++){
				if(d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
				}
			}
		}
	}
	long long ans=1e9;
	for(int i=1;i<=p;i++){
		long long sum=0;
		for(int j=1;j<=n;j++){
			sum=sum+d[mc[j]][i];
		}
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
} 
```

正在渲染内容...