# ABC188 E - Peddler

ABC188 E - Peddler

질문으로 연결

https://atcoder.jp/contests/abc188/tasks/abc188_e

문제 개요

N 개의 거리와 M 개의 일방통행로가 있다.도시 Xi에서 Y까지도로를 통해 i로 이동할 수 있다면 반드시 X를 사용하세요i < Y_네, 맛없어요.
각 거리의 돈의 가격은 A이다네, 어느 도시에서 사서 길로 이동해서 다른 도시에서 팔아요.이윤을 구하다-(돈을 산 가격)의 최대치(때로는 줄어들기도 한다).

구속

2\leqq N\leqq 2 * 10^5
1\leqq M\leqq 2 * 10^5
1\leqq A_i\leqq 10^9
1\leqq X_i < Y_i\leqq N

ABC의 답.

30분 정도 남았기 때문에 중간에 멈췄다.인코딩을 했지만 바로 복습을 다시 썼기 때문에 코드도 남지 않았다.
한쪽 거리만 옆에 정보가 있기 때문에 각 거리의 깊이 우선 탐색에서 먼저 시도해 본 것 같습니다.

공식 해법 1

DAG(Directed Acyclic Graph, CCTV의 지향형 차트 제외)의 경우 다음 DP를 고려할 수 있습니다.(DP를 잘 못해서 일찍 익숙해지고 싶어요)
dp[i]: 거리 i에 도달할 수 있는 거리(거리 i 자신 포함)의 황금의 최저 가격
DP:dp[j]\lefterowmin(dp[j],dp[i],A i) 할당
DP 의 초기 값은 1\leqA 입니다.i\leq10^9 상한보다 큰 10^{10}을 넣습니다.
이렇게 해서 각 dp[i]에서 계산한 후 Ai-dp[i]를 계산하면 최대 값이 대답입니다.
다른 도시에서 움직일 수 없는 거리도 있지만 초기값에 10^{10}을 넣으면 초기값에 따라 달라지지 않기 때문에 Ai-dp[i]는 자연히 최소치가 되어 후보에서 제외된다.

from collections import defaultdict
import numpy as np

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))

G = defaultdict(list)
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)

# dp[i] : 街iに到達できる街 (街i自身を含まない) における金の最安値
# 配るDP : dp[j] <- min(dp[j], dp[i], Ai)
MAX = 10**10
dp = np.array([MAX] * N)
for at in range(N):
    for to in G[at]:
        dp[to] = min(dp[to], dp[at], A[at])

ans = (A - dp).max()
print(ans)

https://atcoder.jp/contests/abc188/submissions/19431144

공식 해법 2

금 거래 가격이 가장 낮은 거리 x1부터 다음 순서대로 행동한다.

x_1부터 도착할 수 있는 모든 거리를 열거하고, xY를 사서 파는 상황에서의 이윤을 기록하다.

기록 y, 이후 작업 중 도착할 수 있는 거리 후보에서 제외.

x_2, x_3\dots 순으로 동일한 작업을 반복합니다.
그 다음 작업에서 도달할 수 있는 거리 후보에서 제외된 이유는 x1, x_2 어느 쪽이든 y에 도달할 수 있다면 x1로 사면 Y로 팔면 더 수지가 맞기 때문에 고려할 필요가 없다.
업무가 끝날 때의 최고 이익에 대답하다.
답안이 때때로 마이너스로 변하기 때문에 초기값에 -10^{10}을 붙일 수 없습니다.
고육계로 나는 첫 번째로 발견한 값을 넣었다.나는 또 어떻게 하면 더 좋을지 조사하고 싶다.

from collections import defaultdict
import numpy as np

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))

G = defaultdict(list)
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)

ranks = np.argsort(A)
seen = np.zeros((N), dtype='bool')

rank = ranks[0]
seen[rank] = True
ans = 0  # -10**10
for key, value in G.items():
    if value:
        ans = A[value[0]] - A[key]
        break
for rank in ranks:
    seen[rank] = True
    q = [rank]
    V = []
    while q:
        at = q.pop()
        for to in G[at]:
            if seen[to]:
                continue
            seen[to] = True
            q.append(to)
            V.append(A[to])
    if V:
        ans = max(ans, max(V) - A[rank])
print(ans)

https://atcoder.jp/contests/abc188/submissions/19432643