算法动态规划

带权DAG上的最长路径：拓扑序DP

字数统计: 2.2k字   |   阅读时长: 10分
, ,

摘要: 拓扑序DP解决带权DAG上的最长路径问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 DAG上的DP (拓扑序DP)：无权 DAG 的最长路径 中我们介绍了 DAG 上的拓扑序 DP，然后解决了无权 DAG 的最长路径的问题。

本文我们来看一下带权 DAG 的最长路径问题。这个问题与 AOE 网的关键路径有密切关系。

指定源点汇点的最长路径

模板题：P1807 最长路

设 G 为有 n 个顶点的带权有向无环图，G 中各顶点的编号为 1 到 n，请设计算法，计算图 G 中 从 1 到 n 间的最长路径。

算法1: 拓扑序 DP

DAG 起点 s 终点 t：

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[u] := 从 u 到 t 的最长路径

答案
dp[s]
dp[u] = INT_MIN / 2 - 1 表示从 u 到不了 t

初始化
dp[t] = 0
dp[u] = INT_MIN / 2

转移
dp[u] = max(dp[v] + e[u][v])
其中 (u, v) 为 v 的入边

由于 DAG 中有些点的入度对 S 到 T 的路径是没影响的，即从 S 到不了点 v 但是 v 却给 S 到 T 的路径提供了入度。

为如果用 BFS 拓扑排序，处理这种情况就很难处理了，如果没有规定起点，可以在连接超级源后用 BFS 拓扑排序。参考 DAG典型应用-活动网络

代码 (C++)

DFS 拓扑序 DP。

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
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

// DFS 拓扑序 DP
struct EdgeTo
{
    int v;
    int w;
    EdgeTo(int v, int w):v(v),w(w){}
};

void dfs(const vector<vector<EdgeTo>>& g, int u, vector<int>& dp)
{
    if(dp[u] != INT_MIN / 2)
        return;
    for(const EdgeTo &son: g[u])
    {
        int v = son.v;
        int w = son.w;
        dfs(g, v, dp);
        if(dp[v] != INT_MIN / 2 - 1 && dp[v] + w > dp[u])
            dp[u] = dp[v] + w;
    }
    if(dp[u] == INT_MIN / 2)
        dp[u] = INT_MIN / 2 - 1;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<EdgeTo>> g(n + 1);
    for(int i = 0; i < m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }
    int s = 1, t = n;
    vector<int> dp(n + 1, INT_MIN / 2);
    dp[t] = 0;
    dfs(g, s, dp);
    if(dp[s] == INT_MIN / 2 - 1)
        cout << -1 << endl;
    else
        cout << dp[s] << endl;
}

算法2: 基于最短路径算法微调

在文章 带权图最短路径 中我们介绍了 Bellman Ford 和 spfa 求最短路径的过程，这里简要回顾：

Bellman Ford

1
2
3
(1) 扫描所有边(x,y,z)：若 d[y] > d[x] + z，则用 d[x] + z 更新 d[y] ，其中 d[x] != INT_MAX / 2
    这步更新与上面的动态规划的转移是一致的
(2) 重复 (A) 直至没有更新操作发生

这里要求最长路径，可以把所有边权取相反数后做最短路径。

代码 (C++)

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
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

// Bellman Ford
struct Edge
{
    int u;
    int v;
    int w;
    Edge(int u, int v, int w):u(u),v(v),w(w){}
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    for(int i = 0; i < m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }
    int s = 1, t = n;
    vector<int> dp(n + 1, INT_MIN / 2);
    dp[s] = 0;
    bool flag = false;
    while(!flag)
    {
        flag = true;
        for(int i = 0; i < m; ++i)
        {
            Edge &e = edges[i];
            if(dp[e.u] != INT_MIN / 2 && dp[e.u] + e.w > dp[e.v])
            {
                flag = false;
                dp[e.v] = dp[e.u] + e.w;
            }
        }
    }
    if(dp[t] == INT_MIN / 2)
        cout << -1 << endl;
    else
        cout << dp[t] << endl;
}

spfa

用一个队列来存储已经被松弛过的点，然后用队列里的点去松弛其他点，就可以避免用一个还没有被松弛的点去松弛另外的点。

1
2
3
4
5
6
建立队列q，初始队列只含有起点 
取队头 x
    扫描与 x 相邻的所有边 (x,y,z)
        若 d[y] > d[x] + z，则用 d[x] + z 更新 d[y]
        若 y 不在队列中，将 y 入队
    重复直至队空

如果所有边权都是同号的，可以考虑做些预处理后变成正边权的最短路径，将队列改为优先级队列。

代码 (C++)

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
#include <vector>
#include <iostream>
#include <climits>
#include <queue>

using namespace std;

// spfa
struct EdgeTo
{
    int v;
    int w;
    EdgeTo(int v, int w):v(v),w(w){}
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<EdgeTo>> g(n + 1);
    for(int i = 0; i < m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }
    int s = 1, t = n;
    vector<int> dp(n + 1, INT_MIN / 2);
    dp[s] = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(EdgeTo son: g[u])
        {
            if(dp[u] + son.w > dp[son.v])
            {
                dp[son.v] = dp[u] + son.w;
                q.push(son.v);
            }
        }
    }
    if(dp[t] == INT_MIN / 2)
        cout << -1 << endl;
    else
        cout << dp[t] << endl;
}

未指定源点汇点的最长路径

模板题：P1113 杂务

John 的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。

当然，有些杂务必须在另一些杂务完成的情况下才能进行。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务 1。

John 有需要完成的 n 个杂务的清单，并且这份清单是有一定顺序的，杂务 $k (k>1)$ 的准备工作只可能在杂务 1 至 $k−1$ 中。

写一个程序依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定 John 的农场有足够多的工人来同时完成任意多项任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
输入格式
第1行：一个整数 n (3<=n<=10,000)，必须完成的杂务的数目；

第 2 至 n+1 行，每行有一些用空格隔开的整数，分别表示：

工作序号（保证在输入文件中是从 1 到 n 有序递增的）；
完成工作所需要的时间 len (1<=len<=100)；
一些必须完成的准备工作，总数不超过 100 个，由一个数字 0 结束。有些杂务没有需要准备的工作只描述一个单独的 0。

保证整个输入文件中不会出现多余的空格。

输出格式
一个整数，表示完成所有杂务所需的最短时间。

输入
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0
输出
23

算法：拓扑序 DP

给定 DAG，未指定源点汇点，求最长路径。AOE 网络求关键活动的其中一步，参考：DAG典型应用-活动网络。

题目中有说明：

至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务1。John有需要完成的n个杂务的清单，并且这份清单是有一定顺序的，杂务k(k>1)的准备工作只可能在杂务1至k-1中。

因此 u 从 1 到 n 已经是拓扑序。直接从 1 到 n 线性推导状态就可以。

建图

建带权有向图 D (邻接表)。

由于题目有说明，以下两步可以省略：

1
2
如果没有入度为零或出度为零的点，则直接返回不可行。
将所有入度为零的点连接一个超级源 SS，边权为 0。将所有出度为零的点连接一个超级汇 ST，边权为 0。

求 SS 到 ST 的最长路径

DAG 起点 s 终点 t：

1
2
3
4
5
6
7
8
9
10
11
dp[v] := 从 s 到 v 的最长路径

答案
dp[t]

初始化
dp[s] = 0

转移
dp[v] = max(dp[u] + e[u][v])
其中 (u, v) 为 v 的入边

代码 (C++)

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
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> dp(n + 1, INT_MIN / 2);
    vector<vector<int>> rg(n + 1);
    vector<int> w(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        int v, t;
        cin >> v >> t;
        int u;
        while((cin >> u) && u != 0)
        {
            rg[v].push_back(u);
        }
        if(rg[v].empty())
            dp[v] = 0;
        w[v] = t;
    }

    int ans = 0;
    for(int v = 1; v <= n; ++v)
    {
        for(int u: rg[v])
            dp[v] = max(dp[v], dp[u] + w[u]);
        ans = max(ans, dp[v] + w[v]);
    }
    cout << ans << endl;
}
Share