zhangxyhp

摘要： \(k\le 20\)，考慮 \(O(2^k)\) 暴力枚舉加入的邊。但是邊數很大，時間復雜度很高無法承受。 考慮在一開始強制選這 \(k\) 條邊，然后跑最小生成樹，此時加入的邊就是一定會加入的邊。設這個邊集為 \(S\)。 將 \(S\) 連接的連通塊縮成點，點數為 \(O(k)\)。再在原圖上 閱讀全文

摘要： A. [COCI2009-2010#7] SVEMIR 顯然 boruvka。將所有點分別按照 \(x\)，\(y\)，\(z\) 排序，更新最小邊。時間復雜度 \(O(n\log^2 n)\)。 Code #include<cstdio> #include<iostream> #include<u 閱讀全文