2012-06-13から1日間の記事一覧
http://poj.org/problem?id=3659 問題 n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。 1 解法 dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。
http://poj.org/problem?id=3659 問題 n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。 1 解法 dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。