Overview

This problem asks us to move water between reservoirs using channels to minimize the difference between the maximum and minimum water levels. Each reservoir must retain at least 1 unit of water after all operations.

Key Observations

The two important observations are: 1. Each connected component is independent: Water cannot be transferred between reservoirs that are not connected by channels, so water levels must be adjusted within each connected component. 2. Conservation of water: Since operations only move water around, the total water within each connected component remains unchanged.

When considering the minimum achievable difference within each connected component, distributing the total water evenly is optimal. However, since water levels must be integers, if the total cannot be divided evenly, some reservoirs will have \(\lfloor \text{average} \rfloor\) and the rest will have \(\lceil \text{average} \rceil\).

Algorithm

1. Decompose the graph into connected components: Use BFS/DFS to decompose the graph into connected components.
2. Analyze each connected component: For each connected component:
   • Compute the number of nodes \(L\) and the total water \(S\)
   • Find the quotient \(q = S \div L\) and remainder \(r = S \mod L\)
   • If \(r=0\), all nodes have water level \(q\); otherwise, \(r\) nodes have \(q+1\) and the rest have \(q\)
3. Determine the global maximum and minimum: Among all connected components, find the maximum of all maximum values (\(q\) or \(q+1\)) and the minimum of all minimum values (\(q\)), then output their difference.

Complexity

• Time complexity: \(O(N + M)\) (connected component decomposition and processing each node)
• Space complexity: \(O(N + M)\) (graph representation and visited array)

Implementation Notes

• Represent the graph as an adjacency list and find connected components using stack-based DFS.

• Since we handle large numbers (on the order of \(10^9\)), be careful about integer overflow (this is not an issue in Python).

• Accurately compute the total water and number of nodes in each connected component, and simulate the even distribution using integer division.

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    P = [0] * (n+1)
    for i in range(1, n+1):
        P[i] = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it))
        graph[u].append(v)
        graph[v].append(u)
    
    visited = [False] * (n+1)
    comps = []  # 各連結成分のノードリスト
    
    for i in range(1, n+1):
        if not visited[i]:
            comp = []
            stack = [i]
            visited[i] = True
            while stack:
                node = stack.pop()
                comp.append(node)
                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)
            comps.append(comp)
    
    global_max = -10**18
    global_min = 10**18
    
    for comp in comps:
        L = len(comp)
        total = 0
        for node in comp:
            total += P[node]
        q = total // L
        r = total % L
        if r == 0:
            comp_min = q
            comp_max = q
        else:
            comp_min = q
            comp_max = q+1
        if comp_max > global_max:
            global_max = comp_max
        if comp_min < global_min:
            global_min = comp_min
            
    print(global_max - global_min)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.1.