P1260: 火星大工程

AOE，拓扑排序，关键路径，http://dsbpython.openjudge.cn/dspythonbook/P1260/

中国要在火星上搞个大工程，即建造n个科考站

建科考站需要很专业的设备，不同的科考站需要不同的设备来完成

有的科考站必须等另外一些科考站建好后才能建。

每个设备参与建完一个科考站后，都需要一定时间来保养维修，才能参与到下一个科考站的建设。

所以，会发生科考站A建好后，必须至少等一定时间才能建科考站B的情况。因为B必须在A之后建，且建B必需的某个设备，参与了建A的工作，它需要一定时间进行维修保养。

一个维修保养任务用三个数a b c表示，意即科考站b必须等a建完才能建。而且，科考站a建好后，建a的某个设备必须经过时长c的维修保养后，才可以开始参与建科考站b。

假设备都很牛，只要设备齐全可用，建站飞快就能完成，建站时间忽略不计。一开始所有设备都齐全可用。

给定一些维修保养任务的描述，求所有科考站都建成，最快需要多长时间。

有的维修保养任务，能开始的时候也可以先不开始，往后推迟一点再开始也不会影响到整个工期。问在不影响最快工期的情况下，哪些维修保养任务的开始时间必须是确定的。按字典序输出这些维修保养工任务，输出的时候不必输出任务所需的时间。

输入

第一行两个整数n,m，表示有n个科考站，m个维修保养任务。科考站编号为1，2.....n 接下来m行，每行三个整数a b c，表示一个维修保养任务 1 < n,m <=3000

输出

先输出所有科考站都建成所需的最短时间然后按字典序输出开始时间必须确定的维修保养任务

样例输入

样例输出

来源

郭炜

python

# 李宗远 白衣者
# 拓扑排序和AOE网络问题
# 首先建立edge对象，依据数据得到邻接矩阵
# 得到拓扑排序序列
# 依据拓扑排序序列得到时间最早和最晚开始时间和最快时长确定关键事件
# 进而确定关键活动
from collections import defaultdict, deque


class Edge:
    def __init__(self, end, weight):
        self.end = end
        self.weight = weight

    def __lt__(self, other):
        return self.end < other.end

def find_critical_activities(n, m, edges):
    # 构建邻接表和入度数组
    graph = defaultdict(list)
    in_degree = [0] * n
    for s, e, w in edges:
        graph[s - 1].append(Edge(e - 1, w))
        in_degree[e - 1] += 1

    # 拓扑排序
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    topological_order = []
    while queue:
        node = queue.popleft()
        topological_order.append(node)
        for edge in graph[node]:
            in_degree[edge.end] -= 1
            if in_degree[edge.end] == 0:
                queue.append(edge.end)

    # 计算最早开始时间
    earliest = [0] * n
    for i in topological_order:
        for edge in graph[i]:
            earliest[edge.end] = max(earliest[edge.end], earliest[i] + edge.weight)
    T = max(earliest)

    # 计算最晚开始时间
    latest = [T] * n
    for j in reversed(topological_order):
        for edge in graph[j]:
            latest[j] = min(latest[j], latest[edge.end] - edge.weight)

    # 确定关键事件
    critical_events = [i for i in range(n) if earliest[i] == latest[i]]

    # 确定关键活动
    critical_activities = []
    for i in critical_events:
        graph[i].sort()
        for edge in graph[i]:
            #关键活动通常指的是导致关键事件发生的活动，而不是所有指向关键事件的活动都是关键活动。
            if edge.end in critical_events and earliest[edge.end] - earliest[i] == edge.weight:
                critical_activities.append((i + 1, edge.end + 1))

    return T, critical_activities


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]

# 求解关键活动
T, critical_activities = find_critical_activities(n, m, edges)

print(T)
for activity in critical_activities:
    print(*activity)

python

from collections import deque, defaultdict
from dataclasses import dataclass


@dataclass
class Edge:
    end: int
    weight: int


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 edge in graph[node]:
            in_degrees[edge.end] -= 1
            if in_degrees[edge.end] == 0:
                queue.append(edge.end)
    return topo_order


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

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

    est = [0] * n
    for node in topo_order:
        for edge in graph[node]:
            est[edge.end] = max(est[edge.end], est[node] + edge.weight)

    T = max(est)

    # 计算最晚开始时间
    lst = [T] * n
    for node in reversed(topo_order):
        for edge in graph[node]:
            lst[node] = min(lst[node], lst[edge.end] - edge.weight)

    # 确定关键事件
    critical_events = [i for i in range(n) if est[i] == lst[i]]

    # 确定关键活动
    critical_activities = []
    for node in critical_events:
        for edge in graph[node]:
            # 关键活动通常指的是导致关键事件发生的活动，而不是所有指向关键事件的活动都是关键活动。
            if edge.end in critical_events and est[node] == est[edge.end] - edge.weight:
                critical_activities.append((node + 1, edge.end + 1))

    # critical_activities.sort()

    return T, ["{} {}".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)]
T, critical_activities = find_critical_activities(n, m, edges)
print(T)
print('\n'.join(critical_activities))

P1260: 火星大工程 ​

P1260: 火星大工程