题解 | 【模板】有依赖的背包问题

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class unionfind{
    private:
        vector<int>par,r;
    public:
        unionfind(int n){
            par.resize(n+1);
            for(int i=1;i<=n;i++){
                par[i]=i;
            }
            r.resize(n+1,0);
        }
        //查找
        int find(int x){
            if(par[x]!=x){
                par[x]=find(par[x]);
            }
            return par[x];
        }
        //合并
        void unionset(int a,int b){
            //找祖宗
            int x=find(a);
            int y=find(b);
            if(x==y){
                return;
            }else if (r[x]>r[y]) {
                par[y]=x;
            }else if (r[x]<r[y]) {
                par[x]=y;
            }else {
                par[y]=x;
                r[x]++;
            }
        }

            // 获取所有集合的映射
        unordered_map<int, vector<int>> getAllSets() {
            unordered_map<int, vector<int>> sets;
            for(int i = 1; i < par.size(); i++) {
                int root = find(i);
                sets[root].push_back(i);
        }
        return sets;
    }
};

int main() {
    int n,m,w;
    cin>>n>>m>>w;
    unionfind uf(n);
    unordered_map<int, pair<int,int>>uv(n);//索引0不使用
    for(int i=1;i<=n;i++){
        int ci,di;
        cin>>ci>>di;
        uv[i]={ci,di};
    }
    for(int i=1;i<=m;i++){
        int ui,vi;
        cin>>ui>>vi;
        uf.unionset(ui, vi);
    }


    vector<pair<int,int>>combinations;
    
    auto sets=uf.getAllSets();

    for(auto &[roots,elements]:sets){
        int price = 0;
        int value = 0;
        for(auto &elem:elements){
            price+=uv[elem].first;//组合的价格
            value+=uv[elem].second;//组合的价值
        }
        combinations.emplace_back(price,value);
    }
    //期望用w购买最多的价值
    vector<int>dp(w+1,0);
    for(auto &com : combinations) {
        for(int j = w; j >= com.first; j--) {  
            dp[j] = max(dp[j], dp[j - com.first] + com.second);
        }
    }
    cout<<dp[w];
    return 0;
}