16562友達bedfs

骨.
これは現在進行中のアルゴリズム研究が当日解決しなければならない問題である.
これはスタックをテーマとした問題であり,問題の発起者はdfsで解決できる問題であるため,スタックを適用して解決する問題であると考えられる.
しかし,この問題の鍵はスタックを利用することではなく,隣接リストを介して友人関係の組合せを確立することである.
これは一般的なdfs問題であるが,友人関係のグループで最も費用がかかるノードを見つける必要があり,これは問題の難易度を高める要因である.
実際、私もdfsを回すだけで、開始ノードの費用だけを格納しているので、一度間違えました.

問題を解く

はすべての友人関係を巡回し始めた.

は、dfsを介して友人関係に関連するノードを検索する.

dfsで探索を行い,接続した友人料金の最小値を更新する.

はすべての巡回を完了し、配列のすべての和を求め、kより小さい場合はその値を出力し、kより大きい場合は費用を支払うことができないためoh noを出力する.

import sys
sys.setrecursionlimit(5000)

N, M, k = map(int, input().split(" "))
expense = list(map(int, input().split(" ")))
visited = [False] * (N+1)
MIN = 0
relationship = [[] for _ in range(N+1)]
min_expense = [0] * (N+1)
payment = 0

for _ in range(M):
    a, b = map(int, input().split(" "))
    relationship[a].append(b)
    relationship[b].append(a)

def solution():
    global payment, MIN

    for i in range(1, N+1):
        if not visited[i]:
            visited[i] = True
            MIN = int(1e9)
            dfs(i)
            min_expense[i] = MIN
    if sum(min_expense) > k:
        print("Oh no")
    else:
        print(sum(min_expense))


def dfs(node):
    global MIN
    MIN = min(MIN, expense[node-1])

    for i in relationship[node]:
        if not visited[i]:
            visited[i] = True
            dfs(i)
    return


solution()