摘要: 拓扑序DP解决带权DAG上的最长路径问题
【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings
在文章 DAG上的DP (拓扑序DP)：无权 DAG 的最长路径 中我们介绍了 DAG 上的拓扑序 DP，然后解决了无权 DAG 的最长路径的问题。
本文我们来看一下带权 DAG 的最长路径问题。这个问题与 AOE 网的关键路径有密切关系。
指定源点汇点的最长路径
设 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;
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;
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;
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;
}
|
未指定源点汇点的最长路径
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;
}
|
