BZOJ 3454 家族：並查集 + 雙指針優化區間選擇

題目大意

無向圖，邊有權值。每個連通塊大小有「喜愛度」。保留邊權在某區間 [L, R] 內的邊，求使總喜愛度 ≥ k 的最小區間長度 R-L。

n ≤ 1000, m ≤ 5000。

解題思路

1. 將邊按權值排序。
2. 雙指針枚舉左端點：固定左端點 i，右端點 j 向右擴展，維護並查集動態加邊。
3. 並查集維護連通塊大小及總喜愛度 `sum`。合併時 `sum -= w[size[x]] + w[size[y]]; sum += w[size[x]+size[y]]`。
4. 若 `sum ≥ k`，更新答案 `ans = min(ans, edge[j].w - edge[i].w)`，並 break 內層循環（因 j 越大區間越長）。
5. 下一輪 i+1 時，需重置並查集。由於 m=5000，O(m² α(n)) 可接受（約 2.5×10⁷ 操作）。

代碼實現 (C++)

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

int fa[N], sz[N];
long long sum, w[N];

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    sum -= w[sz[x]] + w[sz[y]];
    fa[x] = y; sz[y] += sz[x];
    sum += w[sz[y]];
}

int main() {
    int n, m, k;
    while (cin >> n >> m >> k) {
        for (int i = 1; i <= n; i++) cin >> w[i];
        vector edges(m);
        for (auto& e : edges) cin >> e.u >> e.v >> e.w;
        sort(edges.begin(), edges.end(), cmp);
        
        int ans = INT_MAX;
        for (int i = 0; i < m; i++) {
            if (i > 0 && edges[i].w == edges[i-1].w) continue; // 優化：相同權值左端點只需最左
            for (int j = 1; j <= n; j++) { fa[j] = j; sz[j] = 1; }
            sum = 1LL * n * w[1];
            
            for (int j = i; j < m; j++) {
                unite(edges[j].u, edges[j].v);
                if (j+1 == m || edges[j].w != edges[j+1].w) { // 權值變化時檢查
                    if (sum >= k) {
                        ans = min(ans, edges[j].w - edges[i].w);
                        break;
                    }
                }
            }
        }
        if (ans == INT_MAX) cout << "T_T\n";
        else cout << ans << "\n";
    }
}

優化技巧

• 左端點去重：相同權值的邊，只需嘗試最左邊作為左端點。
• 右端點只在權值變化時檢查答案，減少並查集查詢開銷。
• 並查集按秩合併 + 路徑壓縮。