Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-11-01

AddElectricalWires (SRM410 DIV1 Easy)

| 23:06 | AddElectricalWires (SRM410 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - AddElectricalWires (SRM410 DIV1 Easy) - TopCoder煮ブログ

時間はかかったが System Test OK。部分グラフを完全グラフにするまでに必要な枝数をカウントすればよい。gridConnections を含まない部分グラフはノード数が最大の部分グラフに併合する。C++1位の人の答えで答えあわせしたところ、順番に足していっていた。自分の回答は完成図の枝数から最初の枝数を引いていたが、1位の人のほうがスマートだ。あと、グループ分けするときに、自分の回答では幅優先探索していたが、1位の人は頂点の数だけループを回して浸透させていく方式を使っていた。時間が問題にならないのならこっちのほうがシンプルに書ける。