d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://beta.atcoder.jp/contests/agc028/tasks/agc028_c 頂点の重み付き有向グラフが与えられる。各頂点に つの整数が与えられており、 である。頂点 から頂点 への辺の重みは である。すべての頂点をちょうど 回通る有向サイクルの辺の重みの最小値を求めよ。 考え方 未知のものは、「すべての頂点をちょうど 回通る有向サイクルの辺の重みの最小値」である。 の辺の重みの小さいほうから つの辺を選択して有向サイクルを構成したいが、有向サイクルを構成できない場合がある。有向サイクルを構成するための必要条件を整理しよう。 まずすべてが の辺で構成するこ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F10%2F28%2F202836" title="AGC028-C：Min Cost Cycle - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=N Hatena Blog https://hatena.blog 2018-10-28 20:28:36 rich https://tutuz.hateblo.jp/entry/2018/10/28/202836 1.0 100%