概要

この問題は、サーバー間の通信ネットワークを強連結成分（SCC: Strongly Connected Component）に分解し、それぞれの成分ごとに必要な操作回数を求めることで、ネットワーク全体を基準達成にするための最小操作回数を決定する問題です。

考察

1. 操作の性質と強連結成分（SCC）

サーバー \(v\) を選んだときに、レベルが \(1\) 増加するサーバーの集合 \(S(v)\) は、「\(v\) から到達可能、かつ \(v\) へも到達可能」なサーバーの集合です。これは、グラフ理論における強連結成分（SCC）の定義そのものです。

自己ループが存在しないという制約から、各サーバーが属する強連結成分のサイズ（成分に含まれるサーバーの数）によって、以下のように挙動が分かれます。

• サイズが \(1\) の強連結成分（閉路に含まれない単一のサーバー \(u\)）
  • \(u\) から出発して自分自身に戻る経路が存在しないため、\(S(u)\) は空集合となります。
  • したがって、このサーバーのセキュリティレベルを操作によって増加させることは不可能です。
• サイズが \(2\) 以上の強連結成分 \(C\)
  • 成分内の任意のサーバー \(v \in C\) を選ぶことで、集合 \(S(v)\) は \(C\) 全体と一致します。
  • したがって、操作を \(1\) 回行うごとに、成分 \(C\) に属するすべてのサーバーのセキュリティレベルを一律に \(1\) 増加させることができます。

2. 基準達成の可否と最小操作回数の計算

以上の考察から、強連結成分ごとに独立して以下のように処理を行うことができます。

• サイズが \(1\) の成分 \(\{u\}\) の場合
  • 初期値が要求水準に満たない（\(W_u < T_u\)）場合、レベルを上げる手段がないため、どのように操作を行っても基準達成は不可能です。この場合は即座に -1 を出力します。
  • すでに要求水準を満たしている（\(W_u \geq T_u\)）場合は、操作を行う必要はありません。
• サイズが \(2\) 以上の成分 \(C\) の場合
  • 成分内の各サーバー \(u \in C\) が要求水準を満たすためには、少なくとも \(\max(0, T_u - W_u)\) 回の操作が必要です。
  • \(1\) 回の操作で成分内のすべてのサーバーのレベルが同時に \(1\) ずつ増えるため、この成分全体を基準達成にするために必要な最小操作回数は、成分内の各サーバーが必要とする増加量の最大値、すなわち \(\max_{u \in C} (T_u - W_u)\) となります（ただし、全員が最初から要求水準を満たしている場合は \(0\) 回です）。

すべての強連結成分について上記を計算し、不可能なケースがなければ、各成分で必要な操作回数の総和が全体の最小操作回数となります。

アルゴリズム

1. グラフの構築: 与えられた通信回線から有向グラフを隣接リスト形式で構築します。強連結成分分解を行うため、元のグラフ adj と、すべての辺の向きを反転させた逆方向グラフ radj の両方を保持します。

2. 強連結成分分解 (SCC): Kosarajuのアルゴリズムを用いて、グラフを強連結成分に分解します。

   • 1回目のDFS: 元のグラフ adj 上でDFSを行い、帰りがけ順（ポストオーダー）で頂点を記録します。
   • 2回目のDFS: 1回目の帰りがけ順の逆順に、まだ訪問していない頂点から逆方向グラフ radj 上でDFSを行い、到達可能な頂点の集合を1つの強連結成分として抽出します。

3. 成分ごとの判定と集計: 分解された各成分 comp について、サイズに応じて以下のように処理します。

   • len(comp) == 1 のとき: 頂点 \(u\) について \(W_u < T_u\) ならば、-1 を出力して終了。
   • len(comp) > 1 のとき: 成分内の各頂点について \(T_u - W_u\) の最大値を求め、答えに加算する。

計算量

• 時間計算量: \(O(N + M)\)

  • 強連結成分分解（SCC）は、隣接リストを用いたDFSを2回行うことで \(O(N + M)\) で実行可能です。
  • 各強連結成分の判定および最大値の集計処理は、すべての頂点をちょうど1回ずつ走査するため \(O(N)\) です。
  • したがって、全体として \(O(N + M)\) の時間計算量となり、制約 \(N, M \leq 2 \times 10^5\) に対して十分高速に動作します。

• 空間計算量: \(O(N + M)\)

  • グラフの隣接リスト（順方向・逆方向）に \(O(N + M)\)、訪問済みフラグやDFS用のスタック、強連結成分の情報を保持する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 非再帰DFSによるスタックオーバーフローの回避: Pythonでは再帰呼び出しの深さに制限があり、深い再帰は実行速度の低下やメモリの大量消費（最悪の場合はセグメンテーションフォールト）を招きます。本コードでは、明示的にリストを用いたスタック（stack）による非再帰のDFSを実装することで、安全かつ高速に強連結成分分解を行っています。

• 大きな整数への対応: 答え（操作回数の合計）は最大で \(10^9 \times N \approx 2 \times 10^{14}\) に達する可能性があるため、32 bit 整数の範囲を超えます。Pythonでは自動的に多倍長整数が扱われるため意識する必要はありませんが、C++などの静的型付け言語で実装する場合は、答えを保持する変数に long long などの 64 bit 整数型を使用してください。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    W = [int(x) for x in data[2:2+N]]
    T = [int(x) for x in data[2+N:2+2*N]]
    
    adj = [[] for _ in range(N)]
    radj = [[] for _ in range(N)]
    
    idx = 2 + 2*N
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx+1]) - 1
        adj[u].append(v)
        radj[v].append(u)
        idx += 2
        
    order = []
    visited = [False] * N
    for i in range(N):
        if visited[i]:
            continue
        stack = [(i, False)]
        while stack:
            u, processed = stack.pop()
            if processed:
                order.append(u)
                continue
            if visited[u]:
                continue
            visited[u] = True
            stack.append((u, True))
            for v in adj[u]:
                if not visited[v]:
                    stack.append((v, False))
                    
    visited2 = [False] * N
    ans = 0
    for i in reversed(order):
        if visited2[i]:
            continue
        comp = []
        stack = [i]
        visited2[i] = True
        while stack:
            u = stack.pop()
            comp.append(u)
            for v in radj[u]:
                if not visited2[v]:
                    visited2[v] = True
                    stack.append(v)
        
        if len(comp) == 1:
            u = comp[0]
            if W[u] < T[u]:
                print(-1)
                return
        else:
            max_diff = 0
            for u in comp:
                diff = T[u] - W[u]
                if diff > max_diff:
                    max_diff = diff
            ans += max_diff
            
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.5-flash-thinking によって生成されました。