未整理記事
最小全域木
問題
- 最小全域木そのもの
- AOJ GRL_2_A クラスカル法
- AOJ ALDS1_12_A プリム法
- drkenさんのまとめ
- 問題、難しい問題も多く含まれるので注意
- yukicoder No.748 yuki国のお財布事情 解説
- AOJ Building a Space Station
- ARC029 高橋君と国家
- いろはちゃんコンテスト Day2 楽しすぎる家庭菜園 解説
- AOJ 村の道路計画 解説
- 【テク4】AOJ Minimum Spanning Tree
- 【テク1】ARC076 Built? 解説
- AC Gr-idian MST
- 【テク1】【テク2】【テク3】AC Connecting Cities 解説
- 【テク3】AC Tree MST (難)ブルーフカ+全方位木DPでも解ける(想定解)
- 【テク3】AC Interval and MST ブルーフカ
- CF Ozon Tech Challenge 2020 Kuroni and Antihype ブルーフカ
未処理
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