思路与算法

用并查集合并必须同时购买的关系，把每个连通分量的价格、价值求和。每个分量视为一件物品，对预算做倒序01背包。

正确性说明

关系传递闭包内的云必须一起买，且不同分量没有绑定关系，故合法购买集合与分量子集一一对应。倒序01背包恰枚举各分量选或不选，取最大价值即原问题最优值。

复杂度

并查集初始化O(n)，关系处理O((n+m)α(n))，分量汇总O(nα(n))，背包至多O(nW)，总O((n+m)α(n)+nW)，空间O(n+W)。

易错点

不能只合并一层关系，也不能把环重复计价。分量超过预算直接跳过；零预算可空选。累计价值用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, W;
    cin >> n >> m >> W;
    vector<int> p(n), sz(n, 1);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    };
    vector<long long> cost(n), value(n);
    for (int i = 0; i < n; i++)
        cin >> cost[i] >> value[i];
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        u = find(u - 1);
        v = find(v - 1);
        if (u == v)
            continue;
        if (sz[u] < sz[v])
            swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        cost[u] += cost[v];
        value[u] += value[v];
    }
    vector<long long> dp(W + 1);
    for (int u = 0; u < n; u++)
        if (find(u) == u && cost[u] <= W)
            for (int cap = W; cap >= cost[u]; cap--)
                dp[cap] = max(dp[cap], dp[cap - cost[u]] + value[u]);
    cout << dp[W] << '\n';
}