URIOJ 1692 - Curo Attack

Source

Road to Fortaleza III(20141005)
URIOJ 1692

問題概要

ノード数 $N$ の無向木が与えられる.
この木のノードからなる集合で,集合内のノードは連結で,その集合内の最も遠い $2$ ノード間の距離が $K$ となるような集合の要素の数の最大値を求める問題.
そのような集合が存在しないならそれを指摘する.

解法

集合からなる部分木の中心を全て試す.
つまり,$K$ が偶数なら,辺を $1$ つ選び,そこから距離 $K/2$ 以内にあるノードを列挙する.
$K$ が奇数なら,ノードを $1$ つ選び,そこから距離 $(K-1)/2$ 以内にあるノードを列挙する.
その後,最も遠いノード間の距離が $K$ になっているかチェックする,もしくは,列挙するときに確認しながら行う.
時間計算量は $O(N^2)$.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月25日05時29分25秒
Last modified: 2014年11月08日23時16分05秒 (by laycrs)
Tags: Competitive_Programming URI_Online_Judge URI_Contest_20141005_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: