CF741B:https://codeforces.com/problemset/problem/741/B

kyp1229 / 2024-04-26 / 原文

题目描述

大意就是若干人组成某一个连通块，对于每一个人都有一个代价v，和一个魅力值b，选的时候一个集合要么选一个，要么全选，要么不选，求解代价不超过w的前提下所能得到的最大魅力值。
那么我们可以得知这是一道很明显的分组背包问题，关键是用并查集预处理每一物品组

样例

input:
3 1 5
3 2 5
2 4 2
1 2
output:
6

算法1

(dp+并查集) $O(nm)$

C++ 代码

#include<bits/stdc++.h>
using i64=long long;
struct DSU{
    std::vector<int>f,siz;
    DSU(){};
    DSU(int n){
        init(n);
    }
    void init(int n){
        f.resize(n);
        std::iota(f.begin(),f.end(),0);
        siz.assign(n,1);
    }
    int find(int x){
        return f[x]==x?x:find(f[x]);
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y){
            return false;
        }
        if(siz[x]<siz[y]){
            std::swap(x,y);
        }
        siz[x]+=siz[y];
        f[y]=x;
        return true;
    }
    int size(int x){
        return siz[find(x)];
    }
};
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n,m,w;
    std::cin>>n>>m>>w;
    std::vector<int>v(n),b(n);
    for(auto &x:v){
        std::cin>>x;
    }
    for(auto &x:b){
        std::cin>>x;
    }
    DSU dsu(n);
    while(m--){
        int x,y;
        std::cin>>x>>y;
        x--,y--;
        dsu.merge(x,y);
    }
    std::vector<int>g[n];
    for(int i=0;i<n;i++){
        g[dsu.find(i)].push_back(i);
    }
    std::vector<i64>dp(w+1,0);
    for(int i=0;i<n;i++){
        if(dsu.find(i)!=i){
            continue;
        }
        for(int j=w;j>=0;j--){
            int cost=0,val=0;
            for(auto k:g[i]){
                cost+=v[k];
                val+=b[k];
                if(j>=v[k]){
                    dp[j]=std::max(dp[j],dp[j-v[k]]+b[k]);
                }
            }
            if(j>=cost){
                dp[j]=std::max(dp[j],dp[j-cost]+val);
            }
        }
    }
    std::cout<<dp[w]<<"\n";
    return 0;
}