概要

この問題は、有向グラフで表される電力網において、負荷が耐久値を超えた変電所が連鎖的に停電していく様子をシミュレーションし、最終的に停電した変電所をすべて求めるものです。

考察

各変電所には「耐久値」\(T_i\) と「負荷」が定義されており、負荷は初期状態ではその変電所に入ってくる辺（送電線）の本数となっています。もし負荷が耐久値を超えると、その変電所は停電します。停電した変電所からは送電できなくなるため、その先の変電所の負荷が増加します。

この連鎖的な影響をシミュレーションするには、停電する変電所を順番に処理していく必要があります。しかし単純に負荷が耐久値を超えた変電所を適当な順番で処理するのではなく、「最も不安定な変電所」から処理していく必要があります。つまり、負荷と耐久値の差 \(load[i] - T[i]\) が最大のものを優先的に処理するのが効率的です。

このような「最も条件を強く満たす要素を優先的に取り出す」処理には優先度付きキュー（ヒープ）が最適です。これにより、毎回最も不安定な変電所を高速に選び出せます。

また、停電した変電所は以降影響を与えないようにする必要があるため、その情報をフラグで管理します。さらに、負荷の更新は停電していない変電所に対してのみ行います。

アルゴリズム

1. グラフの構築
   　隣接リスト out_edges[u] を用いて、各変電所 \(u\) から出ている辺の先の変電所を管理する。同時に各変電所の初期負荷（入次数）を計算する。

2. 初期状態の準備
   　各変電所の初期負荷を計算し、負荷が耐久値を超えている変電所を優先度付きキューに追加する。このとき、優先度は \(-(load[i] - T[i])\) とすることで、差が大きい順（＝最も不安定な順）に取り出せるようにする。

3. シミュレーション
   　以下の手順を繰り返す：

   • 優先度付きキューから最も不安定な変電所 \(s\) を取り出す。
   • すでに停電していたらスキップ。
   • 停電処理を行い、結果リストに追加。
   • 変電所 \(s\) から出ている辺の先の変電所 \(v\) の負荷を増加させ、もし負荷が耐久値を超えていたらキューに追加。

4. 結果の出力
   　停電した変電所のリストを昇順にソートして出力。なければ -1 を出力。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各頂点および辺についてヒープ操作を行う。ヒープ操作は \(O(\log N)\)。
• 空間計算量: \(O(N + M)\)
  • グラフや各種配列、ヒープのサイズは頂点と辺の数に比例する。

実装のポイント

• 優先度付きキューには (負荷 - 耐久値の負値, 頂点番号) を格納し、最も不安定な変電所を効率良く取り出せるようにする。

• 停電済みかどうかをフラグ管理し、多重処理を防ぐ。

• 入力が多いので sys.stdin.read を使って高速に読み込む。

  ソースコード

import sys
from collections import deque
import heapq

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    T = [0] * (N+1)
    for i in range(1, N+1):
        T[i] = int(data[idx]); idx += 1

    # グラフ構築: adj[v] = list of u such that edge u->v exists
    indeg = [0] * (N+1)
    out_edges = [[] for _ in range(N+1)]  # u -> [v1, v2, ...]
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        out_edges[u].append(v)
        indeg[v] += 1

    # 現在の負荷
    load = indeg[:]
    
    # 停電したか
    stopped = [False] * (N+1)
    
    # 停電候補を管理する優先度付きキュー（負荷 - 耐久値が大きい順）
    # タイブレーカーとして、番号が小さい順
    heap = []
    for i in range(1, N+1):
        if load[i] > T[i]:
            heapq.heappush(heap, (-(load[i] - T[i]), i))
    
    result = []

    while heap:
        # 最も不安定な変電所を取り出す
        neg_diff, s = heapq.heappop(heap)
        if stopped[s] or load[s] <= T[s]:
            continue  # すでに処理済み or 実際には条件を満たさない
        
        stopped[s] = True
        result.append(s)
        
        # 送電先の負荷を増やす
        for v in out_edges[s]:
            if not stopped[v]:
                load[v] += 1
                if load[v] > T[v]:
                    heapq.heappush(heap, (-(load[v] - T[v]), v))

    if result:
        result.sort()
        print(' '.join(map(str, result)))
    else:
        print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。