NIKKEI Programming Contest 2019 - E Weights on Vertices and Edges
問題文
頂点重みX 辺重みY の無向グラフが与えられる. 次の条件を満たすように,なるべく少ない辺を削除したい.
削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。
解法
考察1
削除数を最小化=選択数を最大化.
#考察2
ある辺E_iに注目する.辺E_iの重みをY_iとする.辺重みがY_i以下であるような辺のみで構成されたグラフに対して,辺E_iがすでに条件を満たしているならば,その辺は必ず残すことが出来る.
考察3
辺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)
wrong answer 例
辺集合を重み昇順で見ていく時,「必ず残すことが出来る辺」を見つける度に降順に見ていくアルゴリズム.
すでに「残すことが出来る辺」とマークした辺を再び辿る必要があり,ソートを除いても時間計算量O(N+M)に収まらない.
まとめ
二段階のアルゴリズム. 重み昇順で見ていってマークしたあと,降順でそのマークを使いつつ解を求める.