今度は最小全域木問題に関してまとめてみます。まず、最小全域木問題を解くには2つの方法が知られています。1.プリム法 2.クラスカル法 1.プリム法これはダイクストラ法と似ていて、O(ElogV)のアルゴリズムです。 ある頂点群Vの部分集合であるXとXの補集合を…

ARC031のD問題解こうと思ったら二部グラフの最大流とか言われてうぇええんって感じなので、グラフについて調べつつ忘れないように書いていきます。最短経路問題には3種類の解法があります。 1. ベルマンフォード法 2. ダイクストラ法 3. ワーシャルフロイド…

積み木を並べ替える問題。 BIT使えばO(nlogn)ですね、はい。 問題をもっと簡単に表せる方法を頑張って探せば、こういう問題は楽。 難しく考えない。ちなみに、最初 int res = 0;と書いていて値が大きい時オーバーフローして死んだ。 int は2*1e9くらいまでし…