ずにオンにすることができると思っていたどのように多くのレーダー塔見つけるために:地球上のアルゴリズムは、誰もがそれを解決する方法を知っている場合、私は興味深い問題を考え干渉
は、多くの都市があります。ボブは各都市にレーダータワーを建てました。 各都市は地元の音楽を演奏できるはずだった。
容赦なく、すべてのレーダータワーが互いに干渉しているので、Bob はすべてオフにしなければなりませんでした。
彼は都市間に配置された幸いにもボブを発明した(一部は が地球の中心近くに配置され、いくつかは都市の境界に置かれていた)。
N都市では、N *(N-1)/ 2個のシールドがあります。
残念ながら、多くのシールドが破壊されました。
あなたはそれらの間に盾がない都市のペアが与えられます。
タスクは干渉を発生させることなくオンにすることができるレーダタワーの最大数を見つけることです。
これまで私はこれをグラフとして表現しようとしました(それらの間に遮蔽がない場合、都市は接続されています)。そして、最も一般的な色の数を最大にするグラフの色付けを見つけます。基本的に私は開始ノードを選択し、それを赤にしてから、周囲のノードすべてを青、次に赤にします。もっと速い方法があるかどうか疑問に思っていました。
私は私の研究努力を感謝した –