h_chiro https://blog.hatena.ne.jp/h_chiro/ 雑記 https://h-chiro.hatenablog.com/ PKU http://poj.org/problem?id=3272 概要 DAGが与えられる。 初期地点が入ってくる辺のない点、最終地点が一番番号の大きな点となるようなパスをすべて考えて そのようなパスにもっとも多く入っている辺は、いくつのパスに含まれるか求める問題。 方針 ある点から最終地点までのパスの数と、ある点までのパスの数とをあらかじめ深さ優先探索して求めておく。 すべての辺に対して、(辺の始点までのパスの数)*(辺の終点から最終地点までのパスの数)の最大値が答えになる。 DFSにO(N)、最大値を求めるのにO(M)かかるので全体でO(N+M)になる。 ソース #include<cstdio… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fh-chiro.hatenablog.com%2Fentry%2F20101104%2F1288886383" title=" 3272 Cow Traffic - 雑記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-11-04 00:59:43 rich https://h-chiro.hatenablog.com/entry/20101104/1288886383 1.0 100%