A Bangladeshi Contest at SUST（20151212）
UVa 13038
ノード数 $N$，枝数 $M$ の有向グラフの森が与えられる．
つまり，枝を両向きに通れるとしてもサイクルができないようなグラフが与えられる．
ノードを幾つかのグループに分割するが，ノード $u$ がノード $v$ の祖先（つまりノード $u$ からノード $v$ に辿り着ける）ならば，ノード $u$ とノード $v$ は同じグループに属してはいけない．
もちろん，全てのノードはちょうど $1$ つのグループに属さなかればいけない．
グループの数の最小値を求める問題．
パスに含まれるノードは全て違うグループにしなければいけないので，最も長いパスに含まれるノード数が答え．
動的計画法にて，各ノードからそのノードを始点とする最も長いパスの長さを計算していけば良い．
時間計算量は $O(N)$．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月20日12時39分31秒
Last modified: 2015年12月16日01時49分53秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る
Logged in as: unknown user (not login)