C - Distribution of Water Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は農業用水の管理者です。管轄する地域には N 個の貯水池があり、貯水池は 1 から N までの番号で管理されています。現在、各貯水池 i (1 \leq i \leq N) には P_i リットルの水が蓄えられています。

地域には M 本の水路があり、j 番目の水路は貯水池 U_j と貯水池 V_j を双方向に結んでいます。なお、すべての貯水池が水路を通じて互いにつながっているとは限りません。

高橋君は、すべての貯水池の水量の最大値と最小値の差をできるだけ小さくしたいと考えています。そのために、以下の操作を 0 回以上、好きな回数だけ行うことができます。同じ水路を複数回使うこともできます。

操作： 水路で直接つながっている貯水池の組 (u, v) を 1 つ選び、一方からもう一方へちょうど 1 リットルの水を移動させる。

1 回の操作では水路で直接つながっている貯水池の間でしか水を移動できませんが、操作を繰り返すことで、水路で間接的につながっている貯水池へ水を運ぶこともできます。一方、水路によってつながっていない貯水池の間では、どのように操作を行っても水を移動させることはできません。

ただし、設備の保全上、どの操作の直後においても、すべての貯水池の水量は 1 リットル以上でなければなりません。すなわち、ある操作で貯水池から水を 1 リットル送った結果、その貯水池の水量が 0 リットルになるような操作は行えません。

なお、各貯水池の水量は常に整数リットルです（初期水量が整数であり、操作は 1 リットル単位で行うため）。

操作を最適に行ったとき、すべての貯水池の水量の最大値から最小値を引いた差として達成できる最小の値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • 1 \leq U_j, V_j \leq N
  • U_j \neq V_j（自己ループはない）
  • 同じ貯水池の組を結ぶ水路は高々 1 本である（多重辺はない）
  • 入力はすべて整数である

入力

N M
P_1 P_2 \ldots P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、貯水池の数を表す整数 N と、水路の数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各貯水池の初期水量を表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 続く M 行では、各水路が結ぶ 2 つの貯水池の番号が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) では、j 番目の水路が結ぶ貯水池の番号 U_j と V_j がスペース区切りで与えられる。

出力

操作を最適に行ったとき、すべての貯水池の水量の最大値と最小値の差として達成できる最小の値を 1 行で出力せよ。

入力例 1

3 2
1 5 2
1 2
2 3

出力例 1

1

入力例 2

4 0
3 1 4 1

出力例 2

3

入力例 3

10 8
10 1 7 4 3 20 2 8 8 15
1 2
2 3
3 4
1 4
5 6
6 7
5 7
8 9

出力例 3

10

入力例 4

20 24
100 1 50 75 30 200 10 90 60 5 130 40 1000000000 999999999 2 3 4 500 1 1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 6
2 7
3 8
4 9
13 14
14 15
15 16
16 17
17 18
13 16
14 17
15 18
19 20

出力例 4

333333353

入力例 5

1 0
1000000000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is the manager of agricultural water. The region he manages has N reservoirs, numbered from 1 to N. Currently, each reservoir i (1 \leq i \leq N) stores P_i liters of water.

The region has M waterways, and the j-th waterway bidirectionally connects reservoir U_j and reservoir V_j. Note that it is not necessarily the case that all reservoirs are connected to each other through waterways.

Takahashi wants to minimize the difference between the maximum and minimum water amounts among all reservoirs. To achieve this, he can perform the following operation zero or more times, as many times as he likes. The same waterway can be used multiple times.

Operation: Choose a pair of reservoirs (u, v) that are directly connected by a waterway, and transfer exactly 1 liter of water from one to the other.

In a single operation, water can only be moved between reservoirs that are directly connected by a waterway. However, by repeating operations, water can also be transported to reservoirs that are indirectly connected through waterways. On the other hand, no matter what operations are performed, water cannot be moved between reservoirs that are not connected by any waterways.

However, for equipment maintenance purposes, immediately after every operation, the water amount in every reservoir must be at least 1 liter. That is, an operation that would result in a reservoir having 0 liters of water after sending 1 liter from it is not allowed.

Note that the water amount in each reservoir is always an integer number of liters (since the initial water amounts are integers and operations are performed in units of 1 liter).

When operations are performed optimally, find the minimum achievable value of the difference between the maximum and minimum water amounts among all reservoirs.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • 1 \leq U_j, V_j \leq N
  • U_j \neq V_j (no self-loops)
  • There is at most one waterway connecting the same pair of reservoirs (no multi-edges)
  • All input values are integers

Input

N M
P_1 P_2 \ldots P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains an integer N representing the number of reservoirs and an integer M representing the number of waterways, separated by a space.
  • The second line contains integers P_1, P_2, \ldots, P_N representing the initial water amounts in each reservoir, separated by spaces.
  • The following M lines give the numbers of the two reservoirs connected by each waterway.
  • The (2 + j)-th line (1 \leq j \leq M) contains the reservoir numbers U_j and V_j connected by the j-th waterway, separated by a space.

Output

Print in one line the minimum achievable value of the difference between the maximum and minimum water amounts among all reservoirs when operations are performed optimally.

Sample Input 1

3 2
1 5 2
1 2
2 3

Sample Output 1

1

Sample Input 2

4 0
3 1 4 1

Sample Output 2

3

Sample Input 3

10 8
10 1 7 4 3 20 2 8 8 15
1 2
2 3
3 4
1 4
5 6
6 7
5 7
8 9

Sample Output 3

10

Sample Input 4

20 24
100 1 50 75 30 200 10 90 60 5 130 40 1000000000 999999999 2 3 4 500 1 1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 6
2 7
3 8
4 9
13 14
14 15
15 16
16 17
17 18
13 16
14 17
15 18
19 20

Sample Output 4

333333353

Sample Input 5

1 0
1000000000

Sample Output 5

0