問題
http://community.topcoder.com/stat?c=problem_statement&pm=13759&rd=16461偶奇が二次配列で与えられるのでa[i][j]の偶奇とノードiからノードjへの距離の偶奇が一致すうりょうに木を構成する問題。条件を満たす木が存在しなければ存在しないと答える。
解法
まず対称行列になっているか、a[i][j]+a[j][k]の偶奇とa[i][k]の偶奇が一致するかを確かめる(木なのでdist[i][j]+dist[j][k]=dist[i][k]である)次に,ノードiからノードjへの距離が奇数でありかつiとjが連結でないならば、iからjに枝を張って良い。そしてこの操作を繰り返して木になるならば、それが答えになる。
例えばノード0からスタートして、a[0][i]=Oddとなるようなiに対して0-iで全て枝を張り、張ったiに対してa[i][j]=Oddとなるようなjに対して枝を張り、...ということを繰り返せば良い。
0 件のコメント:
コメントを投稿