Cell Phone Network (PKU 3659)
http://poj.org/problem?id=3659
問題
n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。
1<=n<=10,000
解法
dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。
http://poj.org/problem?id=3659
n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。
1<=n<=10,000
dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。