最长交错路径（Longest Alternating Path in a Directed Graph）

字数 2400 2025-12-12 03:22:50

最长交错路径（Longest Alternating Path in a Directed Graph）

题目描述

给定一个有向无环图（DAG），每条边有一个权重值（正数、负数或零）。我们希望找到图中一条交错路径的最大长度。交错路径的定义是：路径上的边权重严格交替为正和负（即正权重边后面必须跟负权重边，负权重边后面必须跟正权重边，零权重边不能出现在路径中）。路径的长度定义为路径中边的数量。如果图中不存在满足条件的路径，则返回0。

示例
假设图的节点数为4，边如下（格式：起点→终点，权重）：

0→1, +2
1→2, -1
2→3, +3
0→2, -4
1→3, +5

一条可能的交错路径是：0→1（+2），1→2（-1），2→3（+3），长度为3。
另一条：0→2（-4），2→3（+3），长度为2。
最长交错路径长度为3。

约束

节点数 n ≤ 1000
边数 m ≤ 10^4
权重为整数，范围 [-10^4, 10^4]

解题思路

这是一个基于图的线性动态规划问题。由于图是有向无环图（DAG），我们可以利用拓扑顺序进行状态转移，避免了环带来的复杂性。核心是定义合适的状态，并利用边的权重符号进行转移。

状态定义

设 dp[u][sign] 表示以节点 u 为终点的最长交错路径的长度，并且路径的最后一条边的权重符号为 sign，其中 sign 为 0 表示正权重（>0），sign 为 1 表示负权重（<0）。
注意：我们不把零权重边考虑在内，因为零既不满足正也不满足负，无法参与交替。

状态转移

对于每条边 u → v，权重为 w：

如果 w > 0（正边）：
它可以接在一条以 u 为终点且最后一条边为负的路径后面，形成交替。
转移：dp[v][0] = max(dp[v][0], dp[u][1] + 1)。
如果 w < 0（负边）：
它可以接在一条以 u 为终点且最后一条边为正的路径后面，形成交替。
转移：dp[v][1] = max(dp[v][1], dp[u][0] + 1)。

此外，任何一条边本身可以作为一个长度为1的路径，因此初始化时，对于任意边 u→v 权重 w：

若 w > 0，dp[v][0] ≥ 1。
若 w < 0，dp[v][1] ≥ 1。

计算顺序

由于是DAG，我们可以按拓扑排序的顺序依次处理每个节点 u，然后遍历从 u 出发的所有边，更新邻居 v 的 dp 值。这样可以保证在更新 v 时，所有能到达 u 的路径都已经被考虑。

最终答案

答案是所有 dp[u][0] 和 dp[u][1] 中的最大值。

详细步骤

建图与拓扑排序
使用邻接表存储边（包括权重）。计算每个节点的入度，进行拓扑排序，得到节点处理顺序列表 order。
初始化 dp 数组
创建 dp[n][2]，全部初始化为0。
遍历所有边，对于边 u→v, w：
- 若 w > 0，dp[v][0] = max(dp[v][0], 1)。
- 若 w < 0，dp[v][1] = max(dp[v][1], 1)。
动态规划转移
按照拓扑顺序遍历节点 u：
- 对于从 u 出发的每条边 u→v, w：
  - 若 w > 0：dp[v][0] = max(dp[v][0], dp[u][1] + 1)。
  - 若 w < 0：dp[v][1] = max(dp[v][1], dp[u][0] + 1)。
收集答案
遍历所有节点 i 和 sign=0,1，取 dp[i][sign] 的最大值。

举例说明

用前面示例的图：

边列表：
(0,1,+2), (1,2,-1), (2,3,+3), (0,2,-4), (1,3,+5)
拓扑顺序（假设节点编号已拓扑有序）：[0,1,2,3]

初始化 dp（仅基于单边）：

边(0,1,+2)：dp[1][0]=1
(1,2,-1)：dp[2][1]=1
(2,3,+3)：dp[3][0]=1
(0,2,-4)：dp[2][1]=max(1,1)=1（不变）
(1,3,+5)：dp[3][0]=max(1,1)=1

按拓扑顺序转移：

节点0：
- 边(0,1,+2)：dp[1][0] = max(1, dp[0][1]+1) = max(1, 0+1)=1
- 边(0,2,-4)：dp[2][1] = max(1, dp[0][0]+1) = max(1, 0+1)=1
节点1：
- 边(1,2,-1)：dp[2][1] = max(1, dp[1][0]+1) = max(1, 1+1)=2
- 边(1,3,+5)：dp[3][0] = max(1, dp[1][1]+1) = max(1, 0+1)=1
节点2：
- 边(2,3,+3)：dp[3][0] = max(1, dp[2][1]+1) = max(1, 2+1)=3
节点3：无出边。

最终，dp 值：

节点3：dp[3][0]=3, dp[3][1]=0
其他节点最大值小于3。
答案为3，对应路径 0→1(+2), 1→2(-1), 2→3(+3)。

算法复杂度

拓扑排序：O(n + m)
DP 转移：遍历每条边一次，O(m)
总时间复杂度：O(n + m)
空间复杂度：O(n + m) 用于存图和 dp 数组。

关键点总结

利用 DAG 的拓扑序保证无后效性。
状态设计为 dp[u][sign]，sign 表示最后一条边的符号。
转移时严格根据权重的正负号交替。
初始化要包含单边作为路径起点。

这个算法高效地解决了在有向无环图中寻找最长符号交替路径的问题，是线性动态规划在图上的一个典型应用。

最长交错路径（Longest Alternating Path in a Directed Graph）题目描述给定一个有向无环图（DAG），每条边有一个权重值（正数、负数或零）。我们希望找到图中一条交错路径的最大长度。交错路径的定义是：路径上的边权重严格交替为正和负（即正权重边后面必须跟负权重边，负权重边后面必须跟正权重边，零权重边不能出现在路径中）。路径的长度定义为路径中边的数量。如果图中不存在满足条件的路径，则返回0。示例假设图的节点数为4，边如下（格式：起点→终点，权重）：一条可能的交错路径是：0→1（+2），1→2（-1），2→3（+3），长度为3。另一条：0→2（-4），2→3（+3），长度为2。最长交错路径长度为3。约束节点数 n ≤ 1000 边数 m ≤ 10^4 权重为整数，范围 [ -10^4, 10^4 ] 解题思路这是一个基于图的线性动态规划问题。由于图是有向无环图（DAG），我们可以利用拓扑顺序进行状态转移，避免了环带来的复杂性。核心是定义合适的状态，并利用边的权重符号进行转移。状态定义设 dp[u][sign] 表示以节点 u 为终点的最长交错路径的长度，并且路径的最后一条边的权重符号为 sign ，其中 sign 为 0 表示正权重（>0）， sign 为 1 表示负权重（ <0）。注意：我们不把零权重边考虑在内，因为零既不满足正也不满足负，无法参与交替。状态转移对于每条边 u → v ，权重为 w ：如果 w > 0 （正边）：它可以接在一条以 u 为终点且最后一条边为负的路径后面，形成交替。转移： dp[v][0] = max(dp[v][0], dp[u][1] + 1) 。如果 w < 0 （负边）：它可以接在一条以 u 为终点且最后一条边为正的路径后面，形成交替。转移： dp[v][1] = max(dp[v][1], dp[u][0] + 1) 。此外，任何一条边本身可以作为一个长度为1的路径，因此初始化时，对于任意边 u→v 权重 w ：若 w > 0 ， dp[v][0] ≥ 1 。若 w < 0 ， dp[v][1] ≥ 1 。计算顺序由于是DAG，我们可以按拓扑排序的顺序依次处理每个节点 u ，然后遍历从 u 出发的所有边，更新邻居 v 的 dp 值。这样可以保证在更新 v 时，所有能到达 u 的路径都已经被考虑。最终答案答案是所有 dp[u][0] 和 dp[u][1] 中的最大值。详细步骤建图与拓扑排序使用邻接表存储边（包括权重）。计算每个节点的入度，进行拓扑排序，得到节点处理顺序列表 order 。初始化 dp 数组创建 dp[n][2] ，全部初始化为0。遍历所有边，对于边 u→v, w ：若 w > 0 ， dp[v][0] = max(dp[v][0], 1) 。若 w < 0 ， dp[v][1] = max(dp[v][1], 1) 。动态规划转移按照拓扑顺序遍历节点 u ：对于从 u 出发的每条边 u→v, w ：若 w > 0 ： dp[v][0] = max(dp[v][0], dp[u][1] + 1) 。若 w < 0 ： dp[v][1] = max(dp[v][1], dp[u][0] + 1) 。收集答案遍历所有节点 i 和 sign=0,1 ，取 dp[i][sign] 的最大值。举例说明用前面示例的图：边列表： (0,1,+2), (1,2,-1), (2,3,+3), (0,2,-4), (1,3,+5) 拓扑顺序（假设节点编号已拓扑有序）：[ 0,1,2,3 ] 初始化 dp （仅基于单边）：边(0,1,+2)： dp[1][0]=1 (1,2,-1)： dp[2][1]=1 (2,3,+3)： dp[3][0]=1 (0,2,-4)： dp[2][1]=max(1,1)=1 （不变） (1,3,+5)： dp[3][0]=max(1,1)=1 按拓扑顺序转移：节点0：边(0,1,+2)： dp[1][0] = max(1, dp[0][1]+1) = max(1, 0+1)=1 边(0,2,-4)： dp[2][1] = max(1, dp[0][0]+1) = max(1, 0+1)=1 节点1：边(1,2,-1)： dp[2][1] = max(1, dp[1][0]+1) = max(1, 1+1)=2 边(1,3,+5)： dp[3][0] = max(1, dp[1][1]+1) = max(1, 0+1)=1 节点2：边(2,3,+3)： dp[3][0] = max(1, dp[2][1]+1) = max(1, 2+1)=3 节点3：无出边。最终， dp 值：节点3： dp[3][0]=3 , dp[3][1]=0 其他节点最大值小于3。答案为3，对应路径 0→1(+2), 1→2(-1), 2→3(+3)。算法复杂度拓扑排序：O(n + m) DP 转移：遍历每条边一次，O(m) 总时间复杂度：O(n + m) 空间复杂度：O(n + m) 用于存图和 dp 数组。关键点总结利用 DAG 的拓扑序保证无后效性。状态设计为 dp[u][sign] ，sign 表示最后一条边的符号。转移时严格根据权重的正负号交替。初始化要包含单边作为路径起点。这个算法高效地解决了在有向无环图中寻找最长符号交替路径的问题，是线性动态规划在图上的一个典型应用。