【图论】全源最短路 Floyd 算法
算法描述
三个破变量，一共就十行。编程十分钟，运行一晚上。
——全源最短路，Floyd算法打油诗
很多人认为 Floyd 就是简单的动态规划，甚至有人直接把它当模板背了下来，导致不会变通而 WA 了 P1841。然而其实大多数初学者包括我一开始都理解错了它，包括原理。
算法实现
定义 \(dis_{i,j}^k\) 表示只包含前 \(k\) 个节点时 \(i\) 到 \(j\) 的最短路。而加不加入这个 \(k\) 号元素前后有什么区别呢？无非就是某两个点的最短路通过 \(k\) 号点松弛出了更有的最短路嘛。于是就有了经典代码：
void Floyd(){
for(ll k = 1; k <= n; k ++){
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
那么如何初始化呢？如果 \(i\) 到 \(j\) 有路，就初始化为边长。否则初始化为最大值。
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
if(i == j)dis[i][j] = 0;
else if(gph[i][j])dis[i][j] = gph[i][j];
else dis[i][j] = INF;
}
}
这就完了吗？这值得写博客吗？当然不值。虽然我本来就是给自己写来复习的
Floyd应用
Floyd解决传递闭包问题
题目传送门
在有向图中，定义 \(d_{i,j}\) 如果是 1，则表示 \(i\) 能到达 \(j\)，否则反之。
这该如何解决呢？转换一下定义。
定义 \(d_{i,j}^k\) 表示只有前 \(k\) 个点时 \(i\) 能否到达 \(j\)。同理，加入了一个元素 \(k\) 之后无非就是有一组 \(i\) 能通过它到达 \(j\) 了。
void Floyd(){
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
if(graph[i][j])d[i][j] = 1;
else d[i][j] = 0;
}
}
for(ll k = 1; k <= n; k ++){
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
}
}
}
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
cout << d[i][j] << " ";
}
cout << "\n";
}
}
Floyd求最小环
枚举 \(k\) 和小于 \(k\) 的 \(i\) 和 \(j\)，则 dis[i][j] + adj[i][k] + adj[k][j] 可构成包含三个节点的最小环。化简一下，就是在 \(d_{i,j}\) 的基础上加了一个都能到达的元素 \(k\) 构成了一个环。
例题就是刚才在上文说的 P1841 篱笆回路。这题输入特别逆天，所以给了完整代码。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN = 305;
const ll INF = 2147483647;
struct Edge{
ll u, v, w;
bool lside[MAXN], rside[MAXN];
}edge[MAXN];
ll adj[MAXN][MAXN], father[MAXN], m, n, idx[MAXN], dis[MAXN][MAXN];
ll find(ll x){
if(father[x] == x)return x;
return father[x] = find(father[x]);
}
void merge(ll x, ll y){
father[find(x)] = find(y);
}
ll Floyd(){
ll ans = INF;
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
if(!dis[i][j])dis[i][j] = INF;
if(!adj[i][j])adj[i][j] = INF;
}
}
for(ll i = 1; i <= n; i ++){
adj[i][i] = dis[i][i] = 0;
}
for(ll k = 1; k <= n; k ++){
for(ll i = 1; i <= k - 1; i ++){
for(ll j = i + 1; j <= k - 1; j ++){
ans = min(ans, adj[i][k] + adj[k][j] + dis[i][j]);
}
}
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
return ans;
}
int main(){
cin >> m;
for(ll i = 1; i <= m; i ++){
ll s, len, numl, numr, id;
cin >> s >> len >> numl >> numr;
edge[s].u = s * 2 - 1;
edge[s].v = s * 2;
edge[s].w = len;
for(ll j = 1; j <= numl; j ++){
cin >> id;
edge[s].lside[id] = 1;
}
for(ll j = 1; j <= numr; j ++){
cin >> id;
edge[s].rside[id] = 1;
}
}
for(ll i = 1; i <= 250; i ++){
father[i] = i;
}
for(ll i = 1; i <= m; i ++){
for(ll j = 1; j <= m; j ++){
if(i == j)continue;
if(edge[i].lside[j] && edge[j].lside[i]){
merge(edge[i].u, edge[j].u);
}
if(edge[i].lside[j] && edge[j].rside[i]){
merge(edge[i].u, edge[j].v);
}
if(edge[i].rside[j] && edge[j].lside[i]){
merge(edge[i].v, edge[j].u);
}
if(edge[i].rside[j] && edge[j].rside[i]){
merge(edge[i].v, edge[j].v);
}
}
}
for(ll i = 1; i <= 2 * m; i ++){
if(father[i] == i){
idx[i] = ++n;
}
}
for(ll i = 1; i <= m; i ++){
edge[i].u = idx[find(edge[i].u)];
edge[i].v = idx[find(edge[i].v)];
adj[edge[i].u][edge[i].v] = edge[i].w;
adj[edge[i].v][edge[i].u] = edge[i].w;
dis[edge[i].u][edge[i].v] = edge[i].w;
dis[edge[i].v][edge[i].u] = edge[i].w;
}
cout << Floyd() << "\n";
return 0;
}
推荐例题：洛谷 P1119 灾后重建，P1841 重要的城市