燃やす埋める練習問題４ - かんプリンの学習記録

燃やす埋める(Project Selection Problem)の練習問題についての解説です。

ポイント
問題概要
解説
- 操作1のみしか行わない場合
- 操作2も行う場合
提出プログラム
感想

ポイント

${A\rightarrow B}$ (論理包含)タイプの制約

問題概要

${N}$ 頂点 ${M}$ 辺の有向グラフが与えられます． ${i}$ 番目の辺は頂点 ${x_i}$ から頂点 ${y_i}$ へ向かう有向辺です．各頂点には整数 ${B_i}$ が書かれており，各頂点ははじめ白で塗られています．
次の操作を順に行うとき，黒で塗られている頂点に書かれた整数の和の最大値を求めてください．
操作 ${1}$ ： ${0}$ 個以上の頂点を選択し，選択した頂点からたどり着ける頂点を黒で塗る．
操作 ${2}$ ： ${0}$ 個以上の頂点を選択し，選択した頂点からたどり着ける頂点を白で塗る。

${2 \leq N \leq 1000}$
${0 \leq M \leq \min(N(N-1),1000)}$
${0\leq B_i\leq 10^9}$
${1\leq x_i,y_i\leq N}$
${x_i\neq y_i}$
${(x_i,y_i)\neq (x_j,y_j) (i\neq j)}$

解説

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

操作1のみしか行わない場合

操作 ${1}$ のみしか行わない場合はARC085 E - MULと同じようにして解くことができます．
操作 ${1}$ を行った後に，黒で塗られた頂点から白で塗られた頂点へ向かう有向辺が存在してはいけません(黒で塗られた頂点から辿りつける頂点は黒で塗られているはずなので)．したがって，有向辺 ${(u,v)}$ すべてについて頂点 ${u}$ が黒，頂点 ${v}$ が白で塗られている場合に ${\infty}$ のコストをかけるようにすればよいです．
強連結成分はすべて同じ色になりますが，わざわざ強連結成分分解する必要はありません．

操作2も行う場合

操作 ${2}$ で白に塗るのではなく赤に塗ると考えます．すると，先程と同様に考えることができ，黒 ${\rightarrow}$ 白・赤 ${\rightarrow}$ 白・赤 ${\rightarrow}$ 黒，の頂点が存在する場合に ${\infty}$ のコストをかけるようにすればよいです．コストの表とグラフは以下のようになります．