drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AOJ JAG JAG模擬地区 AOJ-ICPC400点 Kruskal法 グラフ 最小全域木 中央値(メディアン)に関する問題 数学的帰納法に基づく考察 最適化の考察：最適解に必ず含まれる要素を列挙する けんちょん本演習問題 そのまま覚えたいシンプル設定の中堅以上の典型問題 グラフの最小全域木の構造に関する理解を問う良問ですね。 問題へのリンク (AOJ) 問題へのリンク 2 (AtCoder) editorials 問題概要 連結な重み付き無向グラフ が与えられます (頂点数 、辺数 )。 の全域木のうち、全域木に含まれる 本の辺の重みのメディアンの最小値を求めてください。 制約 は偶数 解法 グラフ の最小全域木の一つを として、他の任意の全域木を とします。 に含まれる辺の重みを小さい順に として、 に含まれる辺の重みを小さい順に としましょう。 このとき、 が成り立つことが知られています。つまり最小全域木は、 (これは最小全域木の定義です) を満たすだけで… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2021%2F07%2F31%2F124900" title="AOJ 2536 Median Tree (JAG 模擬地区 2012 C) (400 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2021-07-31 12:49:00 rich https://drken1215.hatenablog.com/entry/2021/07/31/124900 1.0 100%