floyd算法
参考AcWing
时间复杂度 \(O(n^3)\)
求多源最短路 ：可以在 \(O(n^3)\) 的时间内求出任意两点的距离
朴素三重循环
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]);
基于dp的思想
扩展的用处
floyd求传递闭包：
用处： 给出 \(a< b\) , \(a< c\) 等不等式， 可以在 \(O(n^3)\) 的时间内计算出 \(a<c\)
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dist[i][j]|= dist[i][k]&& dist[k][j];
栗子：AcWing 343
给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。
不等式之间具有传递性，即若 A>B 且 B>C，则 A>C。
请从前往后遍历每对关系，每次遍历时判断：
如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。
输入格式
输入包含多组测试数据。
每组测试数据，第一行包含两个整数 n 和 m。
接下来 m 行，每行包含一个不等式，不等式全部为小于关系。
当输入一行 0 0 时，表示输入终止。
输出格式
每组数据输出一个占一行的结果。
结果可能为下列三种之一：
如果可以确定两两之间的关系，则输出 "Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次数，'yyy...y'是指升序排列的所有变量。
如果有矛盾，则输出： "Inconsistency found after t relations."，其中't'指迭代次数。
如果没有矛盾，且不能确定两两之间的关系，则输出 "Sorted sequence cannot be determined."。
数据范围
2≤n≤26，变量只可能为大写字母 A∼Z。
输入样例1：
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
输出样例1：
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
输入样例2：
6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0
输出样例2：
Inconsistency found after 6 relations.
输入样例3：
5 5
A<B
B<C
C<D
D<E
E<A
0 0
输出样例3：
Sorted sequence determined after 4 relations: ABCDE.
可以求出传递闭包， 只是判断好像有亿点点麻烦
floyd求最小环
AcWing 344
给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。
先说一下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]);
第 \(k\) 轮的 \(dist[i][j]\) 指的是只用 编号为 \(k-1\) 之内的 \(i-j\) 的最小值， 更新完之后就变成了 用 \(k\) 之内的
而我们找最小环的时候也可以这样推
using namespace std;
#define INF 0x3f3f3f3f
const int N= 105;
int g[N][N], pos[N][N], dist[N][N];
int ans[N];
int cnt;
void get(int i, int j)
{
if(! pos[i][j]) return ;
int k= pos[i][j];
get(i, k); ans[cnt++ ]= k; get(k, j);
return ;
}
int main()
{
int n, m; cin>> n>> m;
memset(g, 0x3f, sizeof g);
while(m-- )
{
int a, b, c; scanf("%d%d%d", &a, &b, &c);
g[a][b]= g[b][a]= min(g[a][b], c);
}
int res= INF;
memcpy(dist, g, sizeof g);
for(int k=1; k<=n; k++)
{
for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++)
if((long long) dist[i][j]+ g[k][j]+ g[k][i]< res)
{
res= dist[i][j]+ g[k][j]+ g[k][i];
cnt= 0;
ans[cnt++ ]= k; ans[cnt++ ]= i;
get(i, j); ans[cnt++ ]= j;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(dist[i][k]+ dist[k][j]< dist[i][j])
{
dist[i][j]= dist[i][k]+ dist[k][j];
pos[i][j]= k;
}
}
if(! cnt) puts("No solution.");
else for(int i=0; i<cnt; i++) cout<< ans[i]<< ' '; cout<< endl;
return 0;
}
更改floyd的状态
给定一张由 T 条边构成的无向图，点的编号为 1∼1000 之间的整数。
求从起点 S 到终点 E 恰好经过 N 条边（可以重复经过）的最短路。
注意: 数据保证一定有解。
\(dp[a+ b][i][j]\) 表示恰好经过 \(a+ b\) 条边 \(i\) 到 \(j\) 的最短路
可以发现递推式
\(dp[a+ b][i][j]= dp[a][i][k]+ dp[b][k][j]\)
四重循环必会超时， 我们可以使用快速幂的思想
using namespace std;
map<int, int> M;
const int N= 1005;
int dist[N][N], ans[N][N], temp[N][N], g[N][N], n;
void mul(int c[][N], int a[][N], int b[][N])
{
memset(temp, 0x3f, sizeof temp);
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
temp[i][j]= min(temp[i][j], a[i][k]+ b[k][j]);
memcpy(c, temp, sizeof temp);
return ;
}
void get(int x)
{
memset(ans, 0x3f, sizeof ans);
for(int i=1; i<=n; i++) ans[i][i]= 0;
while(x)
{
if(x& 1) mul(ans, ans, dist);
mul(dist, dist, dist);
x>>= 1;
}
return ;
}
int main()
{
int m, t, s, e; cin>> m>> t>> s>> e;
memset(g, 0x3f, sizeof g);
for(int i=1; i<=t; i++)
{
int a, b, c; scanf("%d%d%d", &c, &a, &b);
if(! M.count(a)) M[a]= ++ n;
if(! M.count(b)) M[b]= ++ n;
g[M[a]][M[b]]= g[M[b]][M[a]]= min(g[M[a]][M[b]], c);
}
memcpy(dist, g, sizeof g);
if(! M.count(s)) M[s]= ++ n;
if(! M.count(e)) M[e]= ++ n;
get(m);
printf("%d\n", ans[M[s]][M[e]]);
return 0;
}