概要

貯水池の水量を水路を使って移動させ、最大値と最小値の差を最小化する問題です。操作後も各貯水池の水量が1以上である必要があります。

考察

重要な観察は以下の2点です： 1. 連結成分ごとに独立: 水路でつながっていない貯水池間では水の移動ができないため、各連結成分内で水量の調整を行う必要があります 2. 水量の保存則: 操作は水を移動させるだけなので、各連結成分内の水量の合計は変化しません

各連結成分内で達成できる最小の差を考えると、合計水量を均等に分配した場合が最適です。ただし、水量は整数であるため、完全に均等にできない場合は、一部の貯水池が\(\lfloor \text{平均} \rfloor\)、残りが\(\lceil \text{平均} \rceil\)になります。

アルゴリズム

1. グラフの連結成分分解: BFS/DFSを用いてグラフを連結成分に分解します
2. 各連結成分の分析: 各連結成分について：
   • ノード数\(L\)と水量の合計\(S\)を計算
   • 平均値\(q = S \div L\)の商、余り\(r = S \mod L\)を求める
   • \(r=0\)なら全ノードの水量は\(q\)、そうでなければ\(r\)個のノードが\(q+1\)、残りが\(q\)になる
3. 全局的な最大最小の決定: 全ての連結成分の最大値（\(q\)または\(q+1\)）の中の最大値と、最小値（\(q\)）の中の最小値を求め、その差を出力します

計算量

• 時間計算量: \(O(N + M)\)（連結成分分解と各ノードの処理）
• 空間計算量: \(O(N + M)\)（グラフの表現と訪問管理）

実装のポイント

• グラフを隣接リストで表現し、スタックを用いたDFSで連結成分を求めます

• 大きな数値（\(10^9\)レベル）を扱うため、整数演算のオーバーフローに注意（Pythonでは問題ありません）

• 各連結成分の水量合計とノード数を正確に計算し、整数除算で均等分配をシミュレートします

  ソースコード

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

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