ABC 401-500/ABC427C - Bipartize - 競技プログラミング用 知識集積所

---

問題

ABC427C

必要知識

B以下レベルの内容は省略

• 二部グラフ※
• bit全探索※

考え方

頂点数が最大で10しかないため、二部グラフ※にしたときの頂点の塗り方をbit全探索※で全部試しても、そんなに多くない。
1つ1つの彩色に対して、それを二部グラフ※にするために削除すべき辺の数は、辺に対する全探索※で、うっかり同じ色の頂点同士をつないでいる辺が何本あるかを数えればよい。
2^Nパターンの彩色の中で、削除する辺の数が最小だったものが答え。

最悪の入力であっても、グラフの彩色が2^10パターン、それぞれでの辺の全探索※が45本なので、掛け算しても10^8よりも圧倒的に少なく、間に合う。

解答例

解答例

注意点

隣接リスト※や隣接行列※を作る必要はない。

辺の一覧だけで解けるので、手癖でこれらを作るのは時間と労力のロスでしかない。

辺に対するbit全探索※は間に合わない

各辺を消すか残すかでbit全探索※を用意し、できたグラフが二部グラフ※かどうかを幅優先探索※や深さ優先探索※で確認する方法もできそうに見える。
しかし、辺の数は最大45本あり、2^45はさすがに間に合わない。

別解