AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 1192. 奖金

作者: 作者的头像   秀策 ,  2022-01-15 08:49:31 ,  所有人可见 ,  阅读 17


0


N, M = 10010, 20010
n, m = map(int, input().split())
h, e, ne, idx = [-1] * N, [0] * M, [0] * M, 0
q, d, dist = [0] * N, [0] * N, [0] * N


def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1


def topsort():
    hh, tt = 0, -1
    for i in range(1, n + 1):
        if not d[i]:
            tt += 1
            q[tt] = i

    while hh <= tt:
        t = q[hh]
        hh += 1
        i = h[t]
        while i != -1:
            j = e[i]
            d[j] -= 1
            if d[j] == 0:
                tt += 1
                q[tt] = j
            i = ne[i]
    return tt == n - 1


def main():
    for _ in range(m):
        a, b = map(int, input().split())
        add(b, a)
        d[a] += 1

    if not topsort():
        print('Poor Xed')
    else:
        for i in range(1, n + 1):
            dist[i] = 100
        for i in range(n):
            j = q[i]
            k = h[j]
            while k != -1:
                dist[e[k]] = max(dist[e[k]], dist[j] + 1)
                k = ne[k]

        res = 0
        for i in range(1, n + 1):
            res += dist[i]
        print(res)


main()

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息