HDU 4313 Matrix：最小生成樹思想分離機器城市

問題描述

N 城市，N-1 條邊構成樹。K 個城市有機器。需刪除一些邊使任意兩機器城市不連通，每條邊刪除需時 z，一次只能刪一條，求最小總時間（即所需刪除邊權值之和）。

核心觀察

樹上任意兩點唯一路徑。要分離所有機器城市，必須刪除連接不同機器所在連通分量的邊。將每個機器城市視為一個集合，從大到小考慮邊：若一條邊連接兩個都含有機器的集合，則必須刪除它（權值計入答案），並合併集合；否則合併集合但不計入答案。這正是克魯斯克爾最大生成樹的變體。

算法流程

1. 讀入邊，按權值降序排序。
2. 初始化並查集，標記機器城市所在集合 hasMachine[root]=true。
3. 遍歷邊：u=find(x), v=find(y)。若 u!=v：
   　　若 hasMachine[u] && hasMachine[v] → ans += w；
   　　合併：hasMachine[newRoot] = hasMachine[u] || hasMachine[v]。

代碼實現

struct Edge { int u, v; long long w; };
bool cmp(Edge a, Edge b) { return a.w > b.w; }

int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, K; scanf("%d%d", &N, &K);
        vector edges(N-1);
        for (int i=0; i