7 关键路径 3题

M404: 关键路径长度

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1）。判断该图是否是有向无环图，并把顶点视作“事件”、边视作“活动”，求关键路径长度。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数、边数；

接下来m行，每行两个整数u、v、w（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v, 1 \leq w \leq 100$ ），表示一条边的起点和终点的编号及边权。数据保证不会有重边。

输出

如果不是有向无环图，那么只输出No；

如果是有向无环图，那么在第一行输出Yes，第二行输出一个整数，表示关键路径长度。

样例1

输入

输出

Yes
8

解释

对应的有向无环图如下图所示，加粗的边组成了关键路径，其长度为1 + 4 + 3 = 8。

关键路径长度.png

要解决这个问题，我们可以分两个步骤进行：首先判断给定的有向图是否是有向无环图（DAG），如果是的话，再使用拓扑排序结合动态规划来求解关键路径的长度。

关键路径长度

关键路径可以通过以下步骤求得：

拓扑排序：首先进行拓扑排序，确保每一个活动（边）只在其前驱事件（顶点）处理完成后才开始。
动态规划求解：在拓扑排序的基础上，可以通过动态规划来求每个节点的最早开始时间。关键路径的长度即为终点的最早开始时间。

下面是实现这个算法的Python代码：

python

from collections import deque

def find_critical_path(n, m, edges):
    # 构建图
    graph = [[] for _ in range(n)]
    in_degree = [0] * n  # 记录每个节点的入度
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    
    # 拓扑排序
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
    order = []  # 拓扑排序的结果
    while queue:
        u = queue.popleft()
        order.append(u)
        for v, w in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 如果拓扑排序的结果数量小于节点数，说明图中存在环
    if len(order) < n:
        return "No"
    
    # 动态规划求解关键路径长度
    dp = [0] * n  # dp[i]表示从起点到达节点i的最长路径长度
    for u in order:
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
    
    return "Yes\n" + str(max(dp))

if __name__ == "__main__":
    n, m = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    result = find_critical_path(n, m, edges)
    print(result)

M405: 关键活动

https://sunnywhy.com/sfbj/10/7/405

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1）。判断该图是否是有向无环图，并把顶点视作“事件”、边视作“活动”，求出所有的关键活动。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数、边数；

输出

如果不是有向无环图，那么只输出No；

如果是有向无环图，那么在第一行输出Yes，并从第二行开始，每行输出用空格隔开的两个整数，表示关键活动的起点编号和终点编号（注：总是优先输出起点编号较小的关键活动，起点编号相同时优先输出终点编号较小的关键活动）。

样例1

输入

输出

解释

对应的有向无环图如下图所示，加粗的边即为关键活动。

关键路径长度.png

样例2

输入

2 2
1 2 1
2 1 1

输出

No

解释

显然不是有向无环图。

为了解决这个问题，我们可以采用以下策略：

判断有向无环图（DAG）：通过拓扑排序来判断图是否为DAG。如果在拓扑排序过程中所有的顶点都被排序了，那么图是DAG；如果排序过程中存在顶点不能被排序（即存在环），则图不是DAG。
求关键活动：
- 在DAG中，首先通过拓扑排序计算每个顶点的最早开始时间（est）。
- 然后，逆向遍历拓扑排序，计算每个顶点的最晚开始时间（lst）。
- 边u -> v是关键活动，当且仅当est[u] + w(u, v) == lst[v]。

以下是实现上述逻辑的Python代码：

python

from collections import deque, defaultdict

def topo_sort(graph, in_degrees, n):
    queue = deque([i for i in range(n) if in_degrees[i] == 0])
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for adj, weight in graph[node]:
            in_degrees[adj] -= 1
            if in_degrees[adj] == 0:
                queue.append(adj)
    return topo_order if len(topo_order) == n else None

def find_critical_activities(n, m, edges):
    graph = defaultdict(list)
    in_degrees = [0] * n
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degrees[v] += 1

    topo_order = topo_sort(graph, in_degrees, n)
    if topo_order is None:
        return ["No"]

    est = [0] * n
    lst = [float('inf')] * n
    for node in topo_order:
        for adj, weight in graph[node]:
            est[adj] = max(est[adj], est[node] + weight)
    
    lst[topo_order[-1]] = est[topo_order[-1]]
    for node in reversed(topo_order):
        for adj, weight in graph[node]:
            lst[node] = min(lst[node], lst[adj] - weight)
        if node not in graph:  # Leaf node
            lst[node] = min(lst[node], est[node])

    critical_activities = []
    for u, v, w in edges:
        if est[u] + w == lst[v]:
            critical_activities.append((u, v))

    critical_activities.sort()
    return ["Yes"] + ["{} {}".format(u, v) for u, v in critical_activities]

# 读取输入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

# 求解关键活动
result = find_critical_activities(n, m, edges)
for line in result:
    print(line)

这段代码首先尝试对给定的有向图进行拓扑排序。如果成功，说明图是DAG；然后，它计算每个顶点的最早和最晚开始时间，最后找出所有满足条件的关键活动并输出。如果图不是DAG，即存在环，那么拓扑排序的结果不会包含图中的所有顶点，函数将返回“No”。

M406: 关键路径

https://sunnywhy.com/sfbj/10/7/406

现有一个共个顶点、条边的有向图（假设顶点编号为从0到n-1）。判断该图是否是有向无环图，并把顶点视作“事件”、边视作“活动”，求出所有关键路径。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数、边数；

输出

如果不是有向无环图，那么只输出No；

如果是有向无环图，那么在第一行输出Yes，从第二行开始每行输出一条关键路径v[1]->v[2]->...。

注意，路径的输出顺序满足基于整数的字典序，即如果有两条路径a[1]->a[2]->...->a[k]->a[k+1]->...与b[1]->b[2]->...->b[k]->b[k+1]->...，满足a[1]==b[1]、a[2]==b[2]、...、a[k]==b[k]、a[k+1]<b[k+1]，那么把路径a优先输出。

数据保证关键路径条数不超过1000条。

样例1

输入

输出

Yes
0->1->4->5
0->2->4->5

解释

对应的有向无环图如下图所示，加粗的边组成了关键路径，共两条：0->1->4->5、0->2->4->5。

关键路径.png

样例2

输入

2 2
1 2 1
2 1 1

输出

No

解释

显然不是有向无环图。

python

from collections import defaultdict, deque

class Edge:
    def __init__(self, v, w):
        self.v = v
        self.w = w

def topo_sort(n, G, in_degree):
    q = deque([i for i in range(n) if in_degree[i] == 0])
    ve = [0] * n
    topo_order = []

    while q:
        u = q.popleft()
        topo_order.append(u)
        for edge in G[u]:
            v = edge.v
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
            if ve[u] + edge.w > ve[v]:
                ve[v] = ve[u] + edge.w

    if len(topo_order) == n:
        return ve, topo_order
    else:
        return None, None

def get_critical_path(n, G, in_degree):
    ve, topo_order = topo_sort(n, G, in_degree.copy())
    if ve is None:
        return -1, []

    maxLength = max(ve)
    vl = [maxLength] * n

    for u in reversed(topo_order):
        for edge in G[u]:
            v = edge.v
            if vl[v] - edge.w < vl[u]:
                vl[u] = vl[v] - edge.w

    activity = defaultdict(list)
    for u in G:
        for edge in G[u]:
            v = edge.v
            e, l = ve[u], vl[v] - edge.w
            if e == l:
                activity[u].append(v)

    return maxLength, activity

def print_critical_path(u, activity, in_degree, path=[]):
    path.append(u)
    if u not in activity or not activity[u]:
        print("->".join(map(str, path)))
    else:
        for v in sorted(activity[u]):
            print_critical_path(v, activity, in_degree, path.copy())
    path.pop()

# Main
n, m = map(int, input().split())
G = defaultdict(list)
in_degree = [0] * n  # Correctly define in_degree here
for _ in range(m):
    u, v, w = map(int, input().split())
    G[u].append(Edge(v, w))
    in_degree[v] += 1

maxLength, activity = get_critical_path(n, G, in_degree)
if maxLength == -1:
    print("No")
else:
    print("Yes")
    for i in range(n):
        if in_degree[i] == 0:  # Correctly check for start points
            print_critical_path(i, activity, in_degree)

7 关键路径 3题 ​

M404: 关键路径长度 ​

M405: 关键活动 ​

M406: 关键路径 ​

7 关键路径 3题

M404: 关键路径长度

M405: 关键活动

M406: 关键路径