概要

各都市の「需要量 \(S_i\)」と、接続された送電線の「合計送電容量 \(T_i\)」を比較し、\(T_i < S_i\) となる都市の総数を求める問題です。

考察

この問題を解くためのポイントは、各都市の合計送電容量 \(T_i\) をいかに効率よく計算するかにあります。

各都市 \(i\) について、接続されている送電線を一つずつ探すと、最悪の場合 \(O(N \times M)\) の時間がかかってしまい、制約（\(N, M \leq 2 \times 10^5\)）では実行時間制限に間に合いません。

しかし、送電線の情報を順番に見ていき、「その送電線が結んでいる 2 つの都市の供給量に、容量 \(W\) を加算する」という操作を行えば、すべての送電線を 1 回ずつ確認するだけで、全都市の \(T_i\) を求めることができます。

具体的には、以下の手順で進めます： 1. 長さ \(N\) の配列 \(T\) を用意し、すべて \(0\) で初期化する。 2. 各送電線 \((U_j, V_j, W_j)\) について： - 都市 \(U_j\) の供給量に \(W_j\) を足す（\(T_{U_j} \leftarrow T_{U_j} + W_j\)） - 都市 \(V_j\) の供給量に \(W_j\) を足す（\(T_{V_j} \leftarrow T_{V_j} + W_j\)） 3. 全ての送電線を処理した後、各 \(i\) について \(T_i < S_i\) かどうかを判定する。

アルゴリズム

1. 入力の受け取り: 都市数 \(N\)、送電線数 \(M\)、各都市の需要量 \(S_i\) を読み込みます。
2. 供給量の集計:
   • 都市ごとの合計供給量を保持する配列 T を \(0\) で初期化します。
   • \(M\) 本の送電線情報を読み込み、各送電線が結ぶ 2 つの都市のインデックスに対応する T の要素に、送電容量 \(W\) を加算します。
3. 判定とカウント:
   • \(i = 1\) から \(N\) まで順番に、T[i] < S[i] が成り立つか確認します。
   • 条件を満たす都市の数（電力不足の都市数）をカウントします。
4. 出力: カウントした値を解答として出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 需要量の読み込みに \(O(N)\)、送電線の処理に \(O(M)\)、最後の判定に \(O(N)\) かかります。制約内であれば十分に高速です。
• 空間計算量: \(O(N)\)
  • 需要量 \(S\) と合計供給量 \(T\) を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• インデックスの調整: 入力される都市番号は \(1\) から \(N\) ですが、プログラムの配列は通常 \(0\) から始まるため、都市番号から \(1\) を引いて処理するとスムーズです。

• 高速な入出力: \(N\) や \(M\) が大きいため、Python の場合は sys.stdin.read().split() などを使って一括で入力を読み込むと、実行時間の短縮に繋がります。

• 大きな数値への対応: 需要量 \(S_i\) や容量 \(W_j\) は最大 \(10^9\) であり、合計供給量 \(T_i\) はそれを超える可能性があります。Python では整数の大きさに制限がないため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # Read all input data at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to process the input tokens one by one efficiently
    it = map(int, input_data)
    
    try:
        # N: Number of cities, M: Number of power lines
        N = next(it)
        M = next(it)
        
        # S: Demand for each city (S[0] to S[N-1])
        S = [next(it) for _ in range(N)]
        
        # T: Total supply capacity for each city (initialized to 0)
        T = [0] * N
        
        # Process each of the M power lines
        for _ in range(M):
            u = next(it) - 1
            v = next(it) - 1
            w = next(it)
            # Each power line contributes its capacity to both cities it connects
            T[u] += w
            T[v] += w
            
        # Count the number of cities that are power deficient (T_i < S_i)
        deficient_count = 0
        for i in range(N):
            if T[i] < S[i]:
                deficient_count += 1
        
        # Output the total count
        print(deficient_count)
        
    except StopIteration:
        pass

if __name__ == '__main__':
    solve()

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