M30899: 火星大工程

AOE，关键路径，http://cs101.openjudge.cn/practice/30899/

中国要在火星上搞个大工程，即建造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

输出

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

样例输入

9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4

样例输出

18
1 2
2 5
5 7
5 8
7 9
8 9

来源

郭炜

这个问题是一个典型的关键路径（Critical Path Method, CPM）问题。我们可以将科考站看作图的节点，维修保养任务看作带权的有向边。

解题思路

1. 建模：

   • 节点：$n$ 个科考站。
   • 有向边：如果科考站 $b$ 必须在 $a$ 建完并经过 $c$ 时间的维护后才能开工，则建立一条从 $a$ 到 $b$、权重为 $c$ 的边 $(a,b,c)$。
   • 建站时间：题目提到建站时间忽略不计，因此只需考虑边权（维修时间）。

2. 计算最早完成时间 (Earliest Time, ET)：

   • 使用拓扑排序。
   • 初始化所有节点的 $ET$ 为 0（因为一开始所有设备都可用）。
   • 对于每条边 $(u,v,w)$，更新 $ET[v]=max(ET[v],ET[u]+w)$。
   • 所有科考站建成的最短时间即为 $max(ET)$。

3. 计算最晚完成时间 (Latest Time, LT)：

   • 设项目总时长为 $T=max(ET)$。
   • 初始化所有节点的 $LT$ 为 $T$。
   • 按照拓扑排序的逆序处理节点。
   • 对于每条边 $(u,v,w)$，更新 $LT[u]=min(LT[u],LT[v]-w)$。

4. 确定关键任务：

   • 一个任务（边） $(u,v,w)$ 是“必须确定的”（即在关键路径上），当且仅当它的最早开始时间等于最晚开始时间。
   • 数学表达为：$ET[u]==LT[v]-w$。
   • 收集所有满足该条件的边，按字典序排序后输出。

Python 代码实现

import sys
from collections import deque

def solve():
    # 使用 sys.stdin.read().split() 快速读取大数据量
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    adj = [[] for _ in range(n + 1)]
    tasks = [] # 存储原始任务
    in_degree = [0] * (n + 1)
    
    ptr = 2
    for _ in range(m):
        u = int(input_data[ptr])
        v = int(input_data[ptr+1])
        w = int(input_data[ptr+2])
        ptr += 3
        adj[u].append((v, w))
        tasks.append((u, v, w))
        in_degree[v] += 1
        
    # 1. 拓扑排序计算最早完成时间 (ET)
    et = [0] * (n + 1)
    topo_order = []
    # 入度为 0 的站可以从时间 0 开始
    queue = deque([i for i in range(1, n + 1) if in_degree[i] == 0])
    
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v, w in adj[u]:
            if et[u] + w > et[v]:
                et[v] = et[u] + w
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    # 最短总工期
    total_time = max(et) if et else 0
    print(total_time)
    
    # 2. 逆拓扑排序计算最晚完成时间 (LT)
    # 所有终点站最晚必须在 total_time 完成
    lt = [total_time] * (n + 1)
    for u in reversed(topo_order):
        for v, w in adj[u]:
            if lt[v] - w < lt[u]:
                lt[u] = lt[v] - w
                
    # 3. 找出关键任务
    critical_tasks = []
    for u, v, w in tasks:
        # 如果最早开始时间 + 持续时间 == 最晚必须完成时间，则该任务不可延期
        if et[u] == lt[v] - w:
            critical_tasks.append((u, v))
            
    # 4. 按字典序排序输出
    critical_tasks.sort()
    for u, v in critical_tasks:
        print(f"{u} {v}")

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(N+M+M\log M)$。拓扑排序和计算 $ET/LT$ 均为 $O(N+M)$，最后对关键任务排序为 $O(M\log M)$。在 $N,M\le 3000$ 的规模下，运行非常快。
• 空间复杂度：$O(N+M)$，主要用于存储邻接表和各站的时间数组。

# 李宗远 白衣者
# 拓扑排序和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)

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))