PCK2023M (Final) - 点の削除 / Deleting Points
$${d_{\min}}$$を固定し、次の問題を解くことを考えます。
最小で何個の点を削除することで、距離をすべて$${d_{\min}}$$より大きくできるか？
距離が$${d_{\min}}$$以下であるような頂点同士をつないだ無向グラフを用意します。ある点を削除することは、それに対応する頂点とその頂点に接続する辺を削除することだと見做せます。つまり、問題は、「最小で何個の頂点を削除することで、辺を 0 本にできるか？」と言い換えられます。この答えは最小頂点被覆のサイズに等しいです。
頂点の個数は最大で$${N}$$個なので、厳密に最小頂点被覆のサイズを求めるのが難しいです。しかし、$${O(|V|+|E|)}$$時間で動作する2-近似アルゴリズムが知られており、これを適当な回数回すと AC を取れるようです。（$${求めた答え\le K}$$という条件しか必要ないのと、無向グラフの生成方法にクセがあるためでしょうか……？）
提出コード↓
この記事が気に入ったらサポートをしてみませんか？