問題概要
$N$ 頂点 $M $ 辺の単純無向グラフ $G$ が与えられ，頂点 $i$ には整数 $A_i$ が書かれている．
ここで，一つの頂点を削除する以下の操作を $N$ 回繰り返すことでグラフを空にすることを考える．
- まだ削除されていない頂点 $x$ を選ぶ
- $x$ と，$x$ を端点にもつ辺全てを削除する
この操作のコストは，（現存していて）$x$ と隣接している頂点に書かれている整数の和である．
$N$ 回に渡る操作全体のコストを，$N$ 回行った操作のコストの最大値で定義する．操作全体のコストの最小値はいくらか？
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
解法
あまりこういう論調（パターンでどうこうする感じ）は好きではないのですが，あるものはあるということで，キーワードとして「最大値の最小化は二分法」というようなのがあって，蟻本 [1] *1にも載っています．この問題も，二分法を用いて解くことができます*2．
ではどうするかというと，答えの値そのものを二分法で絞り込んでいきます．具体的にはまず，次のような関数を考えます．$$f( G, A, W ) = \text{（全体の）コスト $W$ 以下で全頂点を削除できるか？}$$この $W$ を色々変えて関数値（boolean です）を見ることで二分法を行います．（離散的な関数で？）二分法を行うには単調性が必要とされていますが，今回の場合は大丈夫そうです（単調性を破壊するケースが思いつかない，程度のアレですが）．
となれば，$f$ を実装できれば問題を解くことができます．ここで抑えるべきポイントは 2 つで，
- 適用可能な操作は無条件に適用しても損をしない
- 操作の適用は他の操作のコストを下げ，適用可能な操作を増やしてくれる
です．これらを合わせると，
- 適用可能な操作を適用する
- それによって起こるコストの変化を計算する
- 新たに適用可能になる操作があれば，記憶しておく
といったことを繰り返すことで，与えられた $W$ の元でどれだけ操作を適用できるかが求められます．適用可能な操作が無くなるまでこれを行ったあとで，頂点が全て消えていれば $f$ の値は $\mathit{ True }$ となります．
あとはこれを使って上記の二分法を行うことで答えが求まります．
計算量について
二分法の下限は $-1$ *3で，上限は $N \max\{ A \}$ ですから，この幅を $1$ にするには $\Theta( \log( N \max\{ A \} ) )$ 回の試行が必要です．$f$ の計算にかかる時間は，（同じ頂点を複数回キューに入れたりしないように注意すれば）$O( N + M )$ 時間でできます．
よって全体では $O( ( N + M ) \log( N \max\{ A \} ) )$ 時間となります．
コード
constexpr auto INF = LIM< LL >::max() / 2; bool solve( const VVI &G, const VI &A, const LL W ) { const int N = SZ( G ); VT< LL > ws( N ); queue< int > que; REP( u, N ) { FOR( v, G[u] ) { ws[u] += A[v]; } if ( ws[u] <= W ) { que.push( u ); } } VT< bool > erased( N, false ); while ( !que.empty() ) { const int u = que.front(); que.pop(); erased[u] = true; FOR( v, G[u] ) { if ( erased[v] ) { continue; } if ( W < ws[v] && ( ws[v] -= A[u] ) <= W ) { que.push( v ); } } } return all_of( ALL( erased ), []( const bool b ){ return b; } ); } int main() { cin.tie( nullptr ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; IN( int, N, M ); VI A( N ); cin >> A; VVI G( N ); REP( M ) { IN( int, u, v ); --u, --v; G[u].PB( v ); G[v].PB( u ); } LL lb = -1, ub = INF; while ( lb + 1 < ub ) { const LL mid = ( lb + ub ) / 2; ( solve( G, A, mid ) ? ub : lb ) = mid; } cout << ub << endl; return 0; }
