概要

各都市について「接続している送電線の容量の合計 \(T_i\)」を求め、需要量 \(S_i\) より小さい都市（電力不足の都市）の個数を数える問題です。

考察

都市 \(i\) に供給可能な電力量 \(T_i\) は、都市 \(i\) を端点にもつ送電線の容量の総和です。つまり、各送電線 \((U_j, V_j, W_j)\) は 両端の都市にそれぞれ \(W_j\) ずつ寄与します。

例えば、送電線が \((1,3,5)\) なら、都市1の \(T_1\) に \(+5\)、都市3の \(T_3\) にも \(+5\) されます。

素朴に「各都市ごとに、全ての送電線を見て自分に繋がるものを足す」をすると、
都市数 \(N\) と送電線数 \(M\) が最大 \(2 \times 10^5\) なので、最悪 \(O(NM)\) となり到底間に合いません（約 \(4\times 10^{10}\)）。

そこで発想を逆にして、各送電線を1回だけ処理し、両端の都市の合計値に加算することで、全都市の \(T_i\) を高速に計算できます。

アルゴリズム

1. 配列 \(T\) を長さ \(N\) で用意し、全て \(0\) で初期化する（\(T[i]\) が都市 \(i\) の供給可能量）。
2. 各送電線 \((U, V, W)\) を読み込むたびに、
   • \(T[U] \mathrel{+}= W\)
   • \(T[V] \mathrel{+}= W\) と加算する（都市番号は0-indexに直す）。
3. 最後に全都市 \(i\) について、条件 \(T_i < S_i\) を満たす数を数えて出力する。

計算量

• 時間計算量: \(O(N + M)\)（送電線を1回ずつ処理し、最後に都市を1回見る）
• 空間計算量: \(O(N)\)（\(S\) と \(T\) の配列）

実装のポイント

• 都市番号は入力が \(1\) 始まりなので、内部では \(0\) 始まりにするために -1 する。

• \(W_j\) や \(S_i\) は最大 \(10^9\)、足し合わせは最大で \(2\times 10^5\) 本分になり得ますが、Python の整数は桁あふれしないので安心です。

• 入力サイズが大きいので、sys.stdin.buffer.read() でまとめて読み、イテレータで高速に処理しています。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    S = [next(it) for _ in range(N)]
    T = [0] * N

    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        T[u] += w
        T[v] += w

    ans = sum(1 for i in range(N) if T[i] < S[i])
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。