概要

各都市について、接続する送電線の容量の合計（供給可能電力量）が需要量に満たない都市の数を求める問題です。

考察

この問題で求めるべきことを整理しましょう。

• 各都市 \(i\) に対して、その都市を端点とする全送電線の容量の合計 \(T_i\) を計算する
• \(T_i < S_i\) となる都市の数を数える

重要な気づきとして、送電線は双方向であり、1本の送電線が両方の端点の都市に対してそれぞれ容量分の電力を供給できるという点があります。つまり、送電線 \((U_j, V_j, W_j)\) があれば、\(T_{U_j}\) にも \(T_{V_j}\) にも \(W_j\) が加算されます。

素朴に考えても、各送電線を1回ずつ処理して両端の都市の \(T\) 値に加算すればよく、これは \(O(N + M)\) で十分高速です。特別なアルゴリズムは不要で、丁寧にシミュレーションすれば解けます。

具体例

例えば、\(N = 3\), \(M = 2\), \(S = [10, 5, 8]\) で、送電線が \((1, 2, 7)\) と \((2, 3, 3)\) の場合：

• 都市1: \(T_1 = 7\)（送電線1のみ）→ \(7 < 10\) なので電力不足
• 都市2: \(T_2 = 7 + 3 = 10\)（送電線1と2）→ \(10 \geq 5\) なので十分
• 都市3: \(T_3 = 3\)（送電線2のみ）→ \(3 < 8\) なので電力不足

答えは \(2\) です。

アルゴリズム

1. 各都市の需要量 \(S_i\) を読み込む
2. 配列 \(T\) を長さ \(N\) で \(0\) に初期化する
3. 各送電線 \((U_j, V_j, W_j)\) について、\(T[U_j]\) と \(T[V_j]\) にそれぞれ \(W_j\) を加算する
4. すべての都市 \(i\) について \(T_i < S_i\) となるものの数を数えて出力する

計算量

• 時間計算量: \(O(N + M)\)
  • 需要量の読み込みに \(O(N)\)、送電線の処理に \(O(M)\)、電力不足の判定に \(O(N)\)
• 空間計算量: \(O(N + M)\)
  • 配列 \(S\) と \(T\) にそれぞれ \(O(N)\)、入力の読み込みに \(O(N + M)\)

実装のポイント

• 0-indexed への変換: 入力の都市番号は \(1\) から始まるため、配列のインデックスに合わせて \(-1\) する必要があります。

• オーバーフローに注意: \(W_j\) が最大 \(10^9\) で \(M\) が最大 \(2 \times 10^5\) のため、\(T_i\) は最大で約 \(2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローは起きませんが、C++ などでは long long を使う必要があります。

• 高速入力: Python では sys.stdin.buffer.read() でまとめて読み込むことで、大量の入力を高速に処理できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    T = [0] * N
    for j in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        T[u] += w
        T[v] += w
    ans = sum(1 for i in range(N) if T[i] < S[i])
    print(ans)

main()

この解説は claude4.6opus-thinking によって生成されました。