競技プログラミング総合スレ 64

競技プログラミング総 ..

785:デフォルトの名無しさん
22/12/17 22:54:02.71 ZH4mYY1r0.net
D問題
やり方として
・まずは連結グラフに分解する
・連結グラフが3以上だった場合は無理判定をする
・そして各連結グラフ毎に
とりあえず各頂点に黒と白を割り振って、
このグラフそのものが2部グラフになっているかを判定する
2部グラフになっていた場合に、各連結グラフごとに自信が持ってる
反対の色の頂点数-頂点数をanswerに足していく
そして、各連結グラフについては
グラフ1の黒数×グラフ2の黒数
グラフ1の黒数×グラフ2の白数
グラフ1の白数×グラフ2の黒数
グラフ1の白数×グラフ2の白数
の4つを足す
っていう解法を思いついたんだけど、グラフ問題といたことなかったから、各頂点がどの気に属しているかっていう判定ができなかった
俺のやり方、・まずは連結グラフに分解する
さえクリアできテレバこのやり方であっていた？

次ページ

続きを表示

1を表示