Algorithm14.1.2 Floyd
[TOC]
最短路-Floyd
Floyd - 最短路
（已经经过滚动数组优化，d数组只有两个维度，不需要k这个维度）+邻接矩阵【用mp[maxn][maxn]二维矩阵储存】
- 核心数据结构：只需要一个d数组，经过滚动数组优化之后，只需要两个维度。
- 核心遍历过程：遍历一个中间分割点k，然后遍历两个节点i、j => 分别时d数组的两个维度，来进行遍历
- 最后的结果全部储存在d数组中，包括任意点和任意点的最短路。
#include <iostream>
using namespace std;
const int maxn = 105;
const int inf = (1<<31)-1;
int n, m, d[maxn][maxn], ta, tb, tc;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j) d[i][j] = inf;
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
d[ta][tb] = d[tb][ta] = tc;
}
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][j], d[i][k]+d[k][j]);
return 0;
}
// 测试用例
// 输入
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
// 输出 => 可以得到所有节点之间的距离
0 2 4 3
2 0 2 1
4 2 0 3
3 1 3 0
Floyd - 最小环
https://www.luogu.com.cn/problem/P6175
思路：在每次更新距离之前，先更新一下最小环，双层遍历，遍历ij，看看当前的这个最小环路是多少；然后再更新距离。
#include <iostream>
using namespace std;
const int maxn = 105;
const int inf = 1e8+9;
int n, m, mp[maxn][maxn], d[maxn][maxn], ta, tb, tc, ans = inf;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j) mp[i][j] = d[i][j] = inf;
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
mp[ta][tb] = mp[tb][ta] = d[ta][tb] = d[tb][ta] = tc;
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i < k; ++i)
for (int j = i+1; j < k; ++j)
ans = min(ans, d[i][j]+mp[i][k]+mp[k][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]), d[j][i] = d[i][j];
}
if (ans == inf) printf("No solution.\n");
else printf("%d\n", ans);
return 0;
}
Floyd - 传递闭包
题意：给出已知的大小关系，问可以确定具体排名的个数有多少。
#include <iostream>
using namespace std;
const int maxn = 109;
int n, m, mp[maxn][maxn], ta, tb, ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &ta, &tb);
mp[ta][tb] = 1;
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
for (int i = 1; i <= n; ++i) {
int tem = 0;
for (int j = 1; j <= n; ++j)
if (mp[i][j] || mp[j][i]) tem++;
if (tem == n-1) ans++;
}
printf("%d\n", ans);
return 0;
}
Floyd - 是否存在负权闭环
题目大意：给出一个图，有双向边和单向边（其中单向边的权值是负的），问是否存在路径可以满足起终点一样，权值和为0。
#include <iostream>
using namespace std;
const int maxn = 509;
const int inf = 0x3f3f3f3f;
int t, n, m, w, mp[maxn][maxn], ta, tb, tc;
bool Floyd() {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= n; ++j)
if (mp[i][k]+mp[k][j] < mp[i][j]) mp[i][j] = mp[i][k]+mp[k][j];
if (mp[i][i] < 0) return true; // 判断负权闭环
}
return false;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &w);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j){
if (i == j) mp[i][j] = 0;
mp[i][j] = mp[j][i] = inf;
}
while (m--){
scanf("%d%d%d", &ta, &tb, &tc);
if (tc < mp[ta][tb]) mp[ta][tb] = mp[tb][ta] = tc;
}
while (w--){scanf("%d%d%d", &ta, &tb, &tc);mp[ta][tb] = -tc;}
if (Floyd()) puts("YES");
else puts("NO");
}
return 0;
}