search

customaddone / beginPython

0 stars 0 forks source link

最小全域木 #15

Closed customaddone closed 4 years ago

customaddone commented 4 years ago

064 GRL_2_A - 最小全域木 基本 https://github.com/customaddone/beginPython/blob/dc2e23e93e41f0afef449f478a2c2c631854582c/cgi-bin/index.py

customaddone commented 4 years ago

065 JOI 2010 春合宿 - Finals https://github.com/customaddone/beginPython/blob/16f24abe1178ee4c850770002e2ae96fa17e0c13/cgi-bin/index.py

customaddone commented 4 years ago

085 DSL_1_A - 互いに素な集合 https://github.com/customaddone/beginPython/blob/89db78147c0f397854fdbf67018dae1681246f31/cgi-bin/index.py

customaddone commented 4 years ago

086 AtCoder Beginner Contest 075 C - Bridge 自分以外の辺を繋いで行って全体が１つにまとまっているかそうではないかを見ることでその辺が橋かどうか判断する https://github.com/customaddone/beginPython/blob/d6bb598b60ad9448d91468e60aef099d6ba854de/cgi-bin/index.py

customaddone commented 4 years ago

ABC157 D - Friend Suggestions グラフ問題であればdfsだけでなくUnionFindを疑おう 1と2は友達関係で、1と3はそうではなくて...と言うのはNの大きさから言って無理 事前にO(a * N)の処理を行い、各要素にO(1)の処理を行って求める 入力されるデータについて何が共通していて何が違うのかグルーピングすることが重要 →今回はaとbが同じ集合にあるかどうかが焦点 https://github.com/customaddone/beginPython/blob/079c353b64f26a56c7650f6b25c0d2dce6862fbb/cgi-bin/index.py

customaddone commented 4 years ago

85p 食物連鎖 https://github.com/customaddone/beginPython/blob/2181857a2e6dfd0acadc6742be8d85eac5a1d388/cgi-bin/index.py

customaddone commented 4 years ago

103p conscription 部分最小全域木 https://github.com/customaddone/beginPython/blob/30ab9175d2848fa4e617ee6b2f5c948185f16936/cgi-bin/index.py

customaddone commented 4 years ago

ABC040 D - 道路の老朽化対策について 制限付き通りの数 ①制約的にO(n)ですべての答えを出すか、各queryについてO(1)で答えを出す→ダイクストラは使えない ②今回は最短距離を求める必要はないのでUnionFindを使う ③A年までの橋を許せる人が通れる橋の数 < B年まで許せる人の橋の数(A > B)なので許せる年数でソートする https://github.com/customaddone/beginPython/blob/c57c30de98b93d52a8dcade91c3055885dc27bdf/cgi-bin/index.py

customaddone commented 4 years ago

ABC065 D - Built? ①それぞれのエッジの距離を求めるのはn <= 10 ** 5より無理 ②距離が近い分だけ出してクラスカル法使って行こう→全ての頂点を繋げられるか ③a, bをそれぞれ昇順にしたリストを作成し、上から順にエッジを作っていく　これで全ての頂点がつながる 　あとでedgesをソートすればaで作ったもの、bで作ったもののうち短いものが前に来る https://github.com/customaddone/beginPython/blob/e1acddebde99d46052cc85f14e74c219053f6c36/cgi-bin/index.py