题目描述
大意就是若干人组成某一个连通块,对于每一个人都有一个代价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;
}