GCA

一開始以為是水題結果沒這麼簡單 <a> <a> <d> <d> <f> <f> <a> <b> <c> <c> <e> <e> <g> q 上面測資的答案為 q q q q q q q 需要構圖，再用disjoint Set有連接的縮起來成為一個父節點 記得判斷相衝的狀況 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C::::...

比較好玩的並查集 刪除的話比較麻煩，只要把要刪除的點原來的位置把它無效化，只要給一個映射的值，讓他真正的值在要搬過去的地方即可 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC::::::...

雖然說是普通的MST，可是要考慮蓋機場的錢比造路的錢還要少 這時候比個大小就可以了 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A ...

暴力再用並查集 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:::::A // GGG:::::...