古人已用三冬足,年少今开万卷余。这篇文章主要讲述问题 K: 最勇敢的机器人(并查集+背包)相关的知识,希望能为你提供帮助。
问题 K: 最勇敢的机器人
时间限制: 1 Sec 内存限制: 128 MB
题目描述
机器人们都想知道谁是最勇敢的,于是它们比赛搬运一些物品。
它们到了一个仓库,里面有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行,为最大可能价值
样例输入 Copy
3 10 1
100 1
200 5
10 5
1 2
样例输出 Copy
210
题意: 给出你
思路: 分组背包+并查集
因为a-b,b-c,则a-c也会爆炸所以就是构成几堆物品,每堆中最多拿出一个,多拿出一个,原本拿出来的和刚拿出来的都爆炸了,所以就是把物品分堆,然后用分组背包。
#pragma
#pragma
#include <
immintrin.h>
#pragma
#include <
map>
#include <
queue>
#include <
string>
#include<
iostream>
#include<
stdio.h>
#include<
string.h>
#include <
algorithm>
#include <
math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<
ll,ll>
pii;
#define
#define
#define
#define
#define
const int maxn=1e5+1010;
#define
#define
#define
const int mod=1e9+7;
const int MOD=10007;
inline int read()
int x=0;
bool t=false;
char ch=getchar();
while((ch<
0||ch>
9)&
&
ch!=-)ch=getchar();
if(ch==-)t=true,ch=getchar();
while(ch<
=9&
&
ch>
=0)x=x*10+ch-48,ch=getchar();
return t?-x:x;
ll n,m,k;
ll p[maxn],w[maxn],dp[1010][1010],num[maxn];
ll f[maxn],ans[maxn],cnt;
ll Find(ll x)
if(f[x]==x) return x;
return f[x]=Find(f[x]);
void add(ll x,ll y)
ll fx=Find(x),fy=Find(y);
if(fx!=fy)
f[fx]=fy;
int main()
cin>
>
n>
>
m>
>
k;
for(int i=1;
i<
=n;
i++)
cin>
>
p[i]>
>
w[i];
for(int i=1;
i<
=n;
i++) f[i]=i;
for(int i=1;
i<
=k;
i++)
ll x,y;
cin>
>
x>
>
y;
add(x,y);
for(int i=1;
i<
=n;
i++)
bool flag=0;
for(int j=1;
j<
=cnt;
j++)
if(dp[j][0]==Find(i))
dp[j][++num[j]]=i;
flag=1;
break;
if(flag==0)
dp[++cnt][0]=Find(i);
dp[cnt][++num[cnt]]=i;
for(int i=1;
i<
=cnt;
i++)///组数
for(int j=m;
j>
=0;
j--)
for(int k=1;
k<
=num[i];
k++)
if(j>
=w[dp[i][k]]) ans[j]=max(ans[j],ans[j-w[dp[i][k]]]+p[dp[i][k]]);
cout<
<
ans[m]<
<
endl;
return 0;
【问题 K: 最勇敢的机器人(并查集+背包)】
推荐阅读
- 005.Maven参数配置
- Prime Distance(区间筛)
- 004.maven概念模型图
- Git的分支简单使用
- #导入Word文档图片# 根文件系统制作与挂载
- Docker减小镜像体积
- quarkus下的分布式ID怎么实现
- cat和find 的用法
- C++ 动态内存开辟