はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける最小全域木問題まとめ [MST, プリム, クラスカル, ブルーフカ]

未整理記事

最小全域木

  • 辺に重みが付いている無向グラフが与えられて、ここからいくつかの辺を選んで木を作るとき、重みの総和の最小値は?という問い
  • アルゴリズムは3種類ある 解説
    • プリム法 O(V^2) or O(ElogV)
      • ある頂点を始点として、頂点を1つずつ増やしていく方法
      • O(V^2)の実装は、ダイクストラのような方式で行う
      • グラフが疎の場合に有効
    • クラスカル法 O(ElogE)=O(ElogV)
      • コストの小さい辺から連結できる場合は利用していく方法
      • UnionFindを使って連結判定をする
    • ブルーフカ法 O(ElogV)
      • プリム法を並列化したもの
      • 連結成分毎にプリム法の1ステップを行う
  • 様々な全域木問題
  • テク

最小有向全域木

問題

未処理


http://kmjp.hatenablog.jp/entry/2017/11/12/0930
http://kmjp.hatenablog.jp/entry/2017/07/03/0900
http://kmjp.hatenablog.jp/entry/2016/11/01/1030
http://kmjp.hatenablog.jp/entry/2016/07/10/1000
http://kmjp.hatenablog.jp/entry/2015/12/25/1000
http://kmjp.hatenablog.jp/entry/2015/04/22/1100
http://kmjp.hatenablog.jp/entry/2015/04/14/1000
http://kmjp.hatenablog.jp/entry/2015/03/31/1000
http://kmjp.hatenablog.jp/entry/2014/10/03/0930
http://kmjp.hatenablog.jp/entry/2014/03/11/1000
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e
http://koba-e964.hatenablog.com
http://koba-e964.hatenablog.com/entry/2019/01/02/225036
http://koba-e964.hatenablog.com/entry/2019/01/06/020834
http://koba-e964.hatenablog.com/entry/2018/12/28/160046

https://codeforces.com/problemset/problem/888/G
ブルーフカ
https://codeforces.com/blog/entry/55983
https://codeforces.com/blog/entry/55701

https://csacademy.com/contest/archive/task/rectangle-mst/
ブルーフカ
https://codeforces.com/blog/entry/58198
Hint 1
One natural strategy is to adapt some existing MST algorithms, and exploit the nature of problem to reduce it's time complexity. There are a lot of well known MST algorithms, such as Jarniks-Prim, or Kruskal. However, both have a serious problem — the problem makes it really hard to retrieve single edge weights. What is the workaround?

Hint 2
While less famous than Jarnik and Kruskal's, there is also an algorithm called Borůvka's Algorithm — the first known algorithm for Minimum Spanning Tree. In Boruvka's algorithm, all we have to do is finding a smallest outgoing edge for each component. As some kind of batch processing is allowed now, it sounds that sweep line can help. Can you see how?

Slow Solution
In Borůvka's algorithm, we find a smallest edge leading to other components for each component, and add it to spanning tree. We will instead find a smallest outgoing edge for each node (with different component labels), which we can easily merge for a component.

We will find the smallest outgoing node from 1 to n, in order. As rectangles are events adding constant values in the interval, we can use sweep line approach — the cost of edge outgoing from node i can be maintained in a simple array with O(N) operations per query.

Now, we have to find a node with minimum edge weight, with different component origin, which can be also done in O(N) operations per nodes. Note that Borůvka's algorithm needs careful attention for edges with same costs — If there are ties, picking the one with smallest node number is a good tie-breaking rule. This leads to an O((Q + N)NlgN) time complexity, and O(N) space. It's still too slow, but it's the first algorithm with feasible space complexity.

Full Solution
The bottleneck is in finding minimums, and adding constant value in an interval — which hints toward a segment tree approach. If we were to find a minimum edge weight, without different component restriction, then the problem is a classical lazy propagation — we will omit the details.

To support finding minimum value with different component origin, we can slightly modify the segment tree. For each node, we record two minimums — first one gives minimum value, and second one gives minimum value among the node that have different component than first. This modification still allows lazy propagation and query exactly same as before, so we can do the whole query in O(lgN) time — the complexity is O((Q + N)lg2N). The asymptotics is not huge, but due to the high constant factor of segment tree, the solution doesn't run that fast — that's why we have a huge time limit.



http://drken1215.hatenablog.com/archive/category/最小全域木


https://cf17-final.contest.atcoder.jp/tasks/cf17_final_j

https://atcoder.jp/contests/dwacon5th-final/tasks/dwacon5th_final_c
ブルーフカ

http://drken1215.hatenablog.com/entry/2019/01/15/081500



関係あるだけかも
https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d2-bottle-review.pdf


https://atcoder.jp/contests/dwacon5th-final/tasks/dwacon5th_final_c




http://drken1215.hatenablog.com/entry/2019/01/15/081500


https://betrue12.hateblo.jp/entry/2019/01/14/023707

https://pitsbuffersolution.com/compro/atcoder/arc093e.php
http://kazune-lab.net/contest/2018/03/25/arc093/#

https://kimiyuki.net/writeup/algo/atcoder/code-festival-2016-asapro-1-a/
https://kimiyuki.net/writeup/algo/aoj/1605/

https://www.slideshare.net/chokudai/arc018

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1280
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2511
http://tsutaj.hatenablog.com/entry/2016/12/31/160154
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014%2FPractice%2F模擬地区予選%2F講評&openfile=F.pdf
http://d.hatena.ne.jp/simezi_tan/20130421/1366556126




https://www.creativ.xyz/chu-liu-edmonds-522

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0314

http://icpc.iisf.or.jp/past-icpc/domestic2015/judge/
https://kimiyuki.net/writeup/algo/aoj/1605/
http://competitive-kivantium.hateblo.jp/entry/2016/07/07/230307