A28813. 搭配购买(buy)
填空题
困难
知识点
题目描述
搭配购买(buy)
题目描述
Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，…，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。
输入
第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。
第2~n+1行，每行 ci，di 表示i朵云的价钱和价值。
第n+2~n+1+m行，每行ui，vi，表示买 ui 就必须买vi，同理，如果买 vi 就必须买 ui 。
输出
一行，表示可以获得的最大价值。
输入样例
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2输出样例
1提示
数据范围
30%的数据保证：n≤100；
50%的数据保证：n≤1,000；m≤100；w≤1,000；
100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000。
参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 10005
int n, m, wn;
int fa[N], c[N], d[N];//c[i]：以i为根结点的集合的总价钱 d[i]：i为根结点的集合的总价值
int v[N], w[N], an, dp[N];//背包问题 v:价值 w:重量 dp[j]：前i个物品装入大小为j的背包的最大价值
void init()
{
for(int i = 1; i <= n; ++i)
fa[i] = i;
}
int find(int x)
{
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int i, int j)
{
int x = find(i), y = find(j);
if(x != y)
{
fa[x] = y;
c[y] += c[x];
d[y] += d[x];
}
}
int main()
{
int f, t;
cin >> n >> m >> wn;
init();//并查集初始化
for(int i = 1; i <= n; ++i)
cin >> c[i] >> d[i];
for(int i = 1; i <= m; ++i)//根据输入的关系构成集合
{
cin >> f >> t;
merge(f, t);
}
for(int i = 1; i <= n; ++i)//寻找根结点，将每个集合的价钱和价值提取出来
{
if(fa[i] == i)
{
v[++an] = d[i];
w[an] = c[i];
}
}
for(int i = 1; i <= an; ++i)//01背包问题：有an个商品，第i商品价值v[i]，重量w[i]，背包大小wn。
for(int j = wn; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
cout << dp[wn];
return 0;
}答案解析
有限钱买物品，要价值最大，每件物品只能买一次，能看出这是一个01背包问题。
题目中说：“互相搭配的云要一起买”，并给定了云之间的搭配关系，这就是一种集合关系。这种集合结构可以使用并查集来表示。
互相搭配的云构成一个集合，一个云的集合是一件物品，集合中所有云的价值加和为该物品的价值，集合中所有云的价钱加和为该物品的重量。
因此知道了每件物品的价值和重量，背包大小为这个人拥有的钱数w，用01背包问题的解法即可解决该问题。
上一题
下一题