Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

SRM 303 Knights

|  SRM 303 Knights - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 303 Knights - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6070

ナイトの駒の関係はグラフに帰着できる。

さらに、ナイトの動き方の制約上、駒は大きく分けて二種類に分類でき、

同じ種類の駒が関係を結ぶことはない。

(こういう特別なグラフを「2部グラフ」というらしい)

問題は、グラフのノードを取り除いて、関係(リンク)の無いグラフを作るとき、

取り除く必要のある最小のノード数を求める、というもの。

そして、この問題はどうやら「2部グラフの最大マッチング問題」というものに帰着できるらしい。

確か蟻本に載っていたような気がするので、あとで調べる。