AcWing 1192. 奖金
原题链接
简单
作者:
皓首不倦
,
2020-08-24 23:58:29
,
所有人可见
,
阅读 638
'''
拓扑图上的差分约束问题,转成拓扑排序问题,然后求最长路
'''
import sys
from typing import List
from collections import deque
from collections import Counter
class TopoSort:
# edges是边列表, (a, b)代表一条边,表示a依赖于b, 返回拓扑排序之后的节点列表, 无法完成拓扑排序返回None
# 节点编号是1, 2, 3, .... node_num
@staticmethod
def sort(edges: List, node_num):
dep_cnt = [0] * (node_num + 1) # 每一个节点的依赖计数
price = [100] * (node_num + 1)
link = {}
for a, b in edges:
if b not in link:
link[b] = []
link[b].append(a) # link[b]记录哪些点依赖b
dep_cnt[a] += 1
ans = []
valid_node = deque() # 当前入度为0的所有节点
for node in range(1, node_num + 1):
if dep_cnt[node] == 0:
valid_node.append((node, 100))
last_price = [100] * (node_num + 1)
total = 0
while len(ans) < node_num:
if len(valid_node) == 0:
return None
cur_node, val = valid_node.popleft()
if cur_node in link:
for next in link[cur_node]:
dep_cnt[next] -= 1
if val + 1 > price[next]:
price[next] = val + 1
if dep_cnt[next] == 0:
valid_node.append((next, price[next]))
last_price[next] = price[next]
ans.append(cur_node)
total += val
return total
n, m = map(int, input().split())
edges = []
for i in range(m):
s = sys.stdin.readline()
a, b = map(int, s.split())
edges.append((a, b))
ans = TopoSort.sort(edges, n)
print(ans if ans is not None else 'Poor Xed')
拓扑排序,把各个点排了个序,为啥就能求最长路了