betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング お題箱より。 Problem - B - Codeforces 問題概要 頂点の無向完全グラフがある。このグラフの辺のうち、指定される 本の辺の重みは であり、それ以外の辺の重みは全て である。 このグラフの最小全域木の重み合計を求めよ。 制約 解法 クラスカル法のアルゴリズムより、まずはコスト の辺で連結にできる頂点を全て連結にしてしまい、それから残ったものをコスト の辺で連結にすれば良いです。ただコスト の辺は非常に多いので1つ1つ処理することはできません。 頂点数も辺数も非常に多いケース、例えば である場合を考えましょう。このときコスト の辺は「スカスカ」です。より具体的には、コスト の… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F02%2F24%2F165627" title="Codeforces Round #599 (Div. 1) B. 0-1 MST - ARMERIA" 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=%20n Hatena Blog https://hatena.blog 2020-02-24 16:56:27 rich https://betrue12.hateblo.jp/entry/2020/02/24/165627 1.0 100%