問題文

頂点重みX 辺重みY の無向グラフが与えられる．次の条件を満たすように，なるべく少ない辺を削除したい．

削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。

解法

削除数を最小化＝選択数を最大化．

ある辺E_iに注目する．辺E_iの重みをY_iとする．辺重みがY_i以下であるような辺のみで構成されたグラフに対して，辺E_iがすでに条件を満たしているならば，その辺は必ず残すことが出来る．

辺E_iを含む，辺重みがY_i以下であるような辺のみで構成された連結グラフがあって，辺E_iがすでに条件を満たしているならば，その連結グラフ上の辺はすべて残す事ができる

まず，辺集合を重み昇順で見ていく．

次に，辺集合を重み降順で見ていく．

今見ている辺E_iが「必ず残すことが出来る辺」であることというのは，
- E_iが属しているかつ辺重みY_i以下の辺のみで構成された連結部分グラフの頂点の重み総和がY_iを上回る
- 降順に見ているので，その連結部分グラフの中で最も重い辺は今見ている辺E_i
- E_i以外の辺は重みがY_i以下なので，E_i以外の辺も条件を満たす．
- 連結部分グラフ上の辺はすべて残すことができる．

時間計算量はソートの計算量を無視してO(N+M)

辺集合を重み昇順で見ていく時，「必ず残すことが出来る辺」を見つける度に降順に見ていくアルゴリズム．

すでに「残すことが出来る辺」とマークした辺を再び辿る必要があり，ソートを除いても時間計算量O(N+M)に収まらない．

二段階のアルゴリズム．重み昇順で見ていってマークしたあと，降順でそのマークを使いつつ解を求める．