概要

各都市の電力需要と送電線の容量から、供給電力が需要を下回る「電力不足の都市」の数を求める問題です。

考察

問題文を読むと、各都市 \(i\) の供給可能電力 \(T_i\) は、その都市を端点とするすべての送電線の容量の合計として定義されています。つまり、各送電線の容量を両端の都市にそれぞれ加算することで、各都市の合計供給容量を計算できます。

素朴なアプローチとして、各送電線について両端の都市に容量を加算していき、最後に各都市の \(T_i\) と \(S_i\) を比較する方法が考えられます。この方法は問題の制約内で効率的に動作します。

アルゴリズム

1. 都市数 \(N\) と送電線数 \(M\) を読み込む
2. 各都市の需要量 \(S_1, S_2, \ldots, S_N\) を読み込む
3. 各都市の供給電力量を記録する配列 \(T\) をサイズ \(N+1\) で初期化（0で初期化）
4. 各送電線の情報について:
   • 送電線が結ぶ都市 \(U_j\), \(V_j\) と容量 \(W_j\) を読み込む
   • \(T[U_j]\) に \(W_j\) を加算
   • \(T[V_j]\) に \(W_j\) を加算
5. すべての都市 \(i\) (1から\(N\))について、\(T[i] < S[i-1]\) かどうかをチェック
6. 条件を満たす都市の数をカウントして出力

計算量

• 時間計算量: \(O(N + M)\)
  • 入力読み込みに \(O(N + M)\)
  • 送電線処理に \(O(M)\)
  • 都市のチェックに \(O(N)\)
• 空間計算量: \(O(N)\)
  • 需要量リストと供給量配列の保持に \(O(N)\)

実装のポイント

• 都市の番号が1から始まるため、配列のインデックスに注意が必要です

• 入力データの読み込みを効率的に行うために、一度にすべてのデータを読み込んで処理しています

• 送電線が存在しない場合（\(M = 0\)）でも正しく動作するように、初期化時にすべての \(T_i\) を0に設定しています

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    s_list = list(map(int, data[2:2+n]))
    
    t = [0] * (n + 1)
    
    index = 2 + n
    for _ in range(m):
        u = int(data[index])
        v = int(data[index+1])
        w = int(data[index+2])
        index += 3
        
        t[u] += w
        t[v] += w
        
    count = 0
    for i in range(1, n + 1):
        if t[i] < s_list[i - 1]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。