首页 > 代码库 > 最勇敢的机器人
最勇敢的机器人
【题目描述】
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行，为最大可能价值
【样例输入】
3 10 1
100 1
200 5
10 5
1 2
【样例输出】
210
看到题面，我们就想到了背包问题，但这道题还有其它限制。
我们把放到一起会爆炸的放在同一个集合中，用并查集来维护，这样问题就转化为了集合背包问题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<algorithm> 7 using namespace std; 8 int n,w,k,len,v[1010],c[1010],f[1010],F[1010],s[1010],a[1010][1010]; 9 inline int read()10 {11 int x=0,f=1; char ch=getchar();12 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();}13 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();}14 return x*f;15 }16 int find(int x)17 {18 return f[x]==x?x:f[x]=find(f[x]);19 }20 void work(int x)21 {22 for(int i=1;i<=len;i++)23 if(find(x)==a[i][0]) {s[i]++; a[i][s[i]]=x; return;}24 len++;25 s[len]=1;26 a[len][s[len]]=x;27 a[len][0]=find(x);28 }29 int main()30 {31 n=read(); w=read(); k=read();32 for(int i=1;i<=n;i++)33 f[i]=i;34 for(int i=1;i<=n;i++)35 v[i]=read(),c[i]=read();36 for(int i=1;i<=k;i++)37 {38 int x=read(),y=read();39 x=find(x); y=find(y);40 if(x!=y) f[x]=y;41 }42 for(int i=1;i<=n;i++)43 work(i);44 for(int i=1;i<=len;i++)45 for(int j=w;j>=0;j--)46 for(int k=1;k<=s[i];k++)47 if(j-c[a[i][k]]>=0) F[j]=max(F[j],F[j-c[a[i][k]]]+v[a[i][k]]);48 printf("%d",F[w]);49 return 0;50 }
最勇敢的机器人
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。