@[toc]

简介

Floyd算法是一种区间动态规划，通过不断更新状态的方式来寻求最优解。假如我们有一个图，我们想从其中的A点走到B点，那么最短路一定就是A到B吗，显然不是。可能是A->C->B，也可能是A->D->F->B更短，那么我们怎么求呢？我们可以对每个点都跑一边Dijkstra。不过这样的话时间复杂度就是$O(V(V+E)log_{2}V)$了，如果是稠密图的话，就渐进与$O(V^{3}log_{2}V)$了。而今天介绍的Floyd算法时间复杂度非常简单，就是$O(V^{3})$，而且时间常数非常小，应为它就短短的四行代码：

1
2
3
4
for (int k = 1; k <= n; k++)
 for (int i = 1; i <= n; i++)
  for (int j = 1; j < n; j++)
   dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

其中，这是一个$n*n$的邻接矩阵，而$dis[i][j]$就表示了i到j的最短路。其中k表示目前的中转点编号，而$dis[i][j]$的最小值要么是当前的，要么就是经过k点的，通过枚举所有点作为中转点来一步一步递推出了答案，即不断的状态更新，是动态规划的一个典型应用。

Q1灾后重建

原题传送门->洛谷P1119
在这道题中，每个村庄的路都不一定是通的，但是题目给了一个提示，即村庄修复的时间按标号编号排列时升序的。在Floyd中，最外层的循环枚举的是中转点，而村庄也是恰好升序排列，所以外层循环第一次循环的结果就是只有1号点修好的结果，第二次就是二号点，知道最后修好，所以我们只要把每一层的答案存起来就可以解决问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
#include<functional>
#include<set>
#include<algorithm>
using namespace std;
#define il inline
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define MAX ((int)1e9)
#define ALL 201
int n, m;
int map[ALL][ALL];//地图
int ft[ALL];
il void input()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> ft[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j)
                map[i][j] = MAX;//两个点若不联通，则距离为正无穷
    for (int i = 0; i < m; i++)//输入建图
    {
        int x, y, z;
        cin >> x >> y >> z;
        map[x][y] = map[y][x] = z;
    }
}
int ans[ALL][ALL][ALL];//答案数组
il void floyd()
{
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        for (int i = 0; i < n; i++)//储存每一层答案
            for (int j = 0; j < n; j++)
                ans[k][i][j] = map[i][j];
    }
}
il int find(int t)
{
    for (int i = 0; i < n; i++)
        if (ft[i] > t)
            return i - 1;
    return n - 1;
}
il void query()
{
    int t;
    cin >> t;
    while (t--)
    {
        int x, y, t;
        cin >> x >> y >> t;
        int k = find(t);//寻找这个时间点处于那个村庄修好与相应
        //的下一个村庄修好的中间时间点
        if (t < ft[x] || t < ft[y])//如果时间早于起点或终点修好的时间就输出-1

        {
            cout << -1 << endl;
            continue;
        }
        int a = ans[k][x][y];//获取第k个村庄修好时的i与j之间的最短路
        if (a == MAX)// 如果未联通就输出-1
            cout << -1;
        else
            cout << a;
        cout << endl;
    }
}
int main()
{
    input();
    floyd();
    query();
    return 0;
}

其实Floyd是一个状态压缩的动态规划，它吧枚举中转点的中间状态给压缩了，其实这道题的Floyd可以这样写：

1
2
3
4
5
for (int k = 1; k <= n; k++)
 for (int i = 1; i <= n; i++)
  for (int j = 1; j < n; j++)
   dis[k][i][j] = min(dis[k-1][i][j], dis[k-1][i][k] + dis[k-1][k][j]);

就可以保留下所有状态了。

Q2 Cow Toll Paths

原题传送门->洛谷P2966
其实这道题和上一道题很类似，不过点权的顺序时乱序的，所以我们要先将带你排个序，然后按顺序中转各个点。具体实现看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
#include<functional>
#include<set>
#include<algorithm>
using namespace std;
#define il inline
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define MAX ((int)1e9)
int map[251][251];//不带点权的最短路
int dis[251][251]; //带点权的最短路
struct Point{
    int id, weight;//编号和点权
}point[251];//点集
int ID[251];//记录排序前的编号
int n, m, k; 
il void input()
{
    cin >> n >> m >> k;
    for (int i = 1,x; i <= n; i++)
    {
        cin >> x;
        point[i].id = i, point[i].weight = x;
    }
    sort(point + 1, point + n + 1, [](const Point&l, const Point&r)->bool {return l.weight < r.weight; });//排序
    for (int i = 1; i <= n; i++)//记录
        ID[point[i].id] = i;
    for (int i = 1; i <= n; i++)//初始化
        for (int j = 1; j <= n; j++)
            if (i != j)
                map[i][j] = dis[i][j] = MAX;
    for (int i = 1; i <= m; i++)//建图
    {
        int x, y, z;
        cin >> x >> y >> z;
        map[ID[x]][ID[y]] = map[ID[y]][ID[x]] = min(z, map[ID[x]][ID[y]]);
    }
}
il void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i != j)
                {
                //先跑不带点权的
                    map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
                //因为动态规划的无后效性，所以可以放一起跑
                //距离就是无权最短加上最大点权
                    dis[i][j] = min(dis[i][j], map[i][j] + max(max(point[i].weight, point[j].weight), point[k].weight));
                }
            }
}
il void output()
{
    while (k--)
    {
        int x, y;
        cin >> x >> y;
        cout << dis[ID[x]][ID[y]] << endl;
    }
}
int main()
{
    input();
    floyd();
    output();
    return 0;
}

Q3 Cow Tours

原题传送门->洛谷P1522
这道题可以先用Floyd跑一遍，找出每一个点的联通点中距离最远的，然后枚举每个点的不联通点，将他们联通，然后最大距离就是两个联通点的最大距离加上新连接的边的长度。不过要小心的是，可能不联通才能获得最大的直径，所以联通与否都要比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
#include<functional>
#include<set>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
#define il inline
#define pf(x) ((x)*(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
vector<pair<double, double>> loc;//储存所有点的坐标
double map[151][151];
il double DIS(double x1, double y1, double x2, double y2)//距离公式
{
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
int main()
{
    int n;
    cin >> n;
    loc.resize(n + 1);
    for (int i = 1; i <= n; i++)//输入距离
        cin >> loc[i].first >> loc[i].second;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                map[i][j] = 1e9;
    for(int i=1;i<=n;i++)//邻接矩阵存图
        for (int j = 1; j <= n; j++)
        {
            int x; scanf("%1d", &x);
            if (x)
            {
                map[i][j] = DIS(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
            }
        }
    for (int k = 1; k <= n; k++)//求最短路
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
    double dis[151];//记录每个点与其联通点的最远距离
    double ans1 = 0, ans2 = 1e9;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j] != 1e9)
            {
                dis[i] = max(dis[i], map[i][j]);
            }
            
        }
        ans1 = max(ans1, dis[i]);//找到若不连通的最大直径
    }
    for (int i = 1; i <= n; i++)//枚举所有点
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j] == 1e9)
            {
            //找到最大的联通的直径
                ans2 = min(dis[i] + dis[j] + DIS(loc[i].first, loc[i].second, loc[j].first, loc[j].second), ans2);
            }
        }
    cout << setprecision(6) << fixed;
    cout << max(ans1, ans2);//取最值
    return 0;
}