/ Vijos / 题库 /1250 / 最勇敢的机器人
借鉴博客:http://www.cnblogs.com/chty/p/5830516.html
背景
Wind设计了很多机器人。但是它们都认为自己是最强的,于是,一场比赛开始了~
描述
机器人们都想知道谁是最勇敢的,于是它们比赛搬运一些物品。
它们到了一个仓库,里面有n个物品,每个物品都有一个价值Pi和重量Wi,但是有些物品放在一起会爆炸,并且爆炸具有传递性。(a和b会爆炸、b和c会爆炸则a和c会爆炸)
机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备,于是它们想知道在能力范围内,它们最多可以拿多少价值的物品。
你能帮助它们吗?
格式
输入格式
每组测试数据
第1行为n,Wmax,k(0<=n,Wmax,k<=1000)
接下来n行,为每个物品的Pi,Wi(0<=Pi<=1000,1<=Wi<=10,均为整数)
再接下来k行,每行2个数字a,b表示a和b会发生爆炸
输出格式
对每组数据输出1行
为最大可能价值
样例1
样例输入1
3 10 1
100 1
200 5
10 5
1 2
样例输出1
210
限制
每个测试点1s
提示
来源
Wind
解题思路:并查集维护分组+分组背包求解
好久没做过分组背包了,套路:枚举每一组,枚举质量,最后枚举每一组中的每一个
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm> #define N 10101010
using namespace std; void in(int &x){
register char c=getchar();x=;int f=;
while(!isdigit(c)){if(c=='-') f=-;c=getchar();}
while(isdigit(c)){x=x*+c-'';c=getchar();}
x*=f;
} int n,w,k,W[N],v[N],fa[N],f[],ans,g[N];
vector<int>V[];
int find(int u){return fa[u]==u?u:find(fa[u]);}
bool vis[N]; int main()
{
in(n);in(w);in(k);
for(int i=;i<=n;i++) in(v[i]),in(W[i]),fa[i]=i;
for(int i=;i<=k;i++){
int u,v,fu,fv;
in(u);in(v);
fu=find(u);fv=find(v);
if(fu!=fv){
fa[fu]=fv;
}
}
for(int i=;i<=n;i++){
fa[i]=find(i);
if(fa[i]==i) g[++g[]]=i;
V[fa[i]].push_back(i);
}for(int i=;i<=g[];i++){
for(int k=w;k>=;k--){
for(int j=;j<V[g[i]].size();j++){
int q=V[g[i]][j];
if(k>=W[q]) f[k]=max(f[k],f[k-W[q]]+v[q]);//防止数组越界
}
}
}printf("%d\n",f[w]);
return ;
}