ABC256E - Takahashi's Anguish

考え方

アライグマ「E問題はサイクルを見つける問題なのだ！　誰からも嫌われてない子にキャンディをあげていくと、嫌い関係がサイクルになってるところが残るのだ。サイクルのうち一番不満度が小さいところを諦めればいいのだ！」 pic.twitter.com/jAyeXiLO9f

— 競技プログラミングをするフレンズ (@kyopro_friends) June 18, 2022

回答例

ある頂点からスタートして，辺をたどっていき，2回見た頂点が出てきたらサイクルに入っている．その頂点を起点にもう一度ずつサイクルを見ていく．

一回見たサイクルを，違う頂点からスタートして何度も見る可能性があるため，seen_localを作って判定する．seen_localで見ていないのに，seenですで見ているなら，そのサイクルの寄与は加算済みである．

seen_localをリストでforの中で毎回生成するとTLEする．setにするのが良い．

N = int(input())
X = list(map(int, input().split()))
C = list(map(int, input().split()))

G = [X[i] - 1 for i in range(N)]

seen = [False] * N
ans = 0
for i in range(N):
    if seen[i]:continue
    cur = i
    seen_local = set()
    ans_local = 0
    while True:
        if seen[cur] and (cur not in seen_local):break
        if cur in seen_local:
            ans_local = C[cur]
            nxt = G[cur]
            while nxt != cur:
                ans_local = min(ans_local, C[nxt])
                nxt = G[nxt]
            break
        seen[cur] = True
        seen_local.add(cur)
        cur = G[cur]
    ans += ans_local

print(ans)