Overview

This is a problem where, for each city, we need to find the number of cities where the total capacity of connected power lines (available power supply) is less than the city’s demand.

Analysis

Let’s organize what we need to compute in this problem.

• For each city \(i\), calculate the total capacity \(T_i\) of all power lines that have that city as an endpoint
• Count the number of cities where \(T_i < S_i\)

An important observation is that power lines are bidirectional, and a single power line can supply its capacity’s worth of power to both endpoint cities. In other words, if there is a power line \((U_j, V_j, W_j)\), then \(W_j\) is added to both \(T_{U_j}\) and \(T_{V_j}\).

Even with a straightforward approach, we just need to process each power line once and add to the \(T\) values of both endpoint cities, which runs in \(O(N + M)\) and is sufficiently fast. No special algorithm is needed — careful simulation is enough to solve this.

Concrete Example

For example, with \(N = 3\), \(M = 2\), \(S = [10, 5, 8]\), and power lines \((1, 2, 7)\) and \((2, 3, 3)\):

• City 1: \(T_1 = 7\) (only power line 1) → \(7 < 10\) so power shortage
• City 2: \(T_2 = 7 + 3 = 10\) (power lines 1 and 2) → \(10 \geq 5\) so sufficient
• City 3: \(T_3 = 3\) (only power line 2) → \(3 < 8\) so power shortage

The answer is \(2\).

Algorithm

1. Read the demand \(S_i\) for each city
2. Initialize array \(T\) of length \(N\) with \(0\)
3. For each power line \((U_j, V_j, W_j)\), add \(W_j\) to both \(T[U_j]\) and \(T[V_j]\)
4. Count and output the number of cities \(i\) where \(T_i < S_i\)

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading demands, \(O(M)\) for processing power lines, \(O(N)\) for checking power shortages
• Space complexity: \(O(N + M)\)
  • \(O(N)\) each for arrays \(S\) and \(T\), \(O(N + M)\) for reading input

Implementation Notes

• Converting to 0-indexed: Since city numbers in the input start from \(1\), you need to subtract \(-1\) to match array indices.

• Beware of overflow: Since \(W_j\) can be up to \(10^9\) and \(M\) can be up to \(2 \times 10^5\), \(T_i\) can reach approximately \(2 \times 10^{14}\). In Python, integer overflow does not occur, but in C++ and similar languages, you need to use long long.

• Fast input: In Python, reading all input at once with sys.stdin.buffer.read() allows for fast processing of large inputs.

  Source Code

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()

This editorial was generated by claude4.6opus-thinking.