ある都市に供給可能な電力量の定義は、その都市を端点とする送電線の容量の合計でした。

都市ごとに求めるのではなく「送電線を張るごとに、その両端の都市に供給可能な電力量が増える」と考えることで、送電線のない状態から始めて、各都市に現時点で供給可能な電力量を更新していけばよいです。

計算量は \(O(N+M)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> s(n);
  for(int i=0; i<n; i++) cin >> s[i];

  vector<long long> t(n);
  for(int i=0; i<m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    t[u] += w;
    t[v] += w;
  }

  int ans = 0;
  for(int i=0; i<n; i++){
    if(t[i] < s[i]){
      ans++;
    }
  }

  cout << ans << endl;
}

実装例 (Python)

N, M = map(int, input().split())
S = list(map(int, input().split()))

T = [0] * N
for _ in range(M):
  U, V, W = map(int, input().split())
  U -= 1
  V -= 1
  T[U] += W
  T[V] += W

ans = 0
for i in range(N):
  if T[i] < S[i]:
    ans+=1

print(ans)