搭配购买
题目描述
明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 $n$ 朵云，云朵已经被老板编号为 $1,2,3,…,n$，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。
输入格式
第一行输入三个整数，$n,m,w$，表示有 $n$ 朵云，$m$ 个搭配和你现有的钱的数目。
第二行至 $n+1$ 行，每行有两个整数， $c_i,d_i$，表示第 $i$ 朵云的价钱和价值。
第 $n+2$ 至 $n+1+m$ 行 ，每行有两个整数 $u_i,v_i$。表示买第 $u_i$ 朵云就必须买第 $v_i$ 朵云,同理，如果买第 $v_i$ 朵就必须买第 $u_i$ 朵。
输出格式
一行，表示可以获得的最大价值。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
9
| 5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
|
样例输出 #1
提示
- 对于 $30\%$ 的数据，满足 $1 \le n \le 100$；
- 对于 $50\%$ 的数据，满足 $1 \le n, w \le 10^3$，$1 \le m \le 100$；
- 对于 $100\%$ 的数据，满足 $1 \le n, w \le 10^4$，$0 \le m \le 5 \times 10^3$。
题解
题目解析
最近刚学到并查集, 现在就用到了. 这道题需要不断将两个物品链接, 这样的话我们自然而然的想到并查集.
然后最蛋疼的是我知道这是并查集之后我不知道如何维护这个价值的集合. 问了问同学, 看了看题解. 然后我懂了这道题. 我们完全可以遍历一遍并查集, 发现不是根节点就把它的价钱和价值存到头节点, 原先的节点归零. 这样又形成新的物品, 不断维护就好了.
维护之后就是正常的背包题目了, 套路题.
东灯同学说这样归零不单独提出来有值的数组是危险操作, 但是我比较懒, 下次一定.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;
MAXN(1e4);
int dp[MAXN],a[MAXN],b[MAXN],head[MAXN];
int find(int x){
if(head[x] != x) head[x] = find(head[x]);
return head[x];
}
signed main(){
CIN_;CIN;
int n,m,w;
cin >> n >> m >> w;
fa(i,1,n){
head[i] = i;
cin >> a[i] >> b[i];
}
fa(i,1,m){
int x,y;
cin >> x >> y;
head[find(x)] = find(y);
}
fa(i,1,n){
if(head[i] != i){
b[find(i)] += b[i];
b[i] = 0;
a[find(i)] += a[i];
a[i] = 0;
}
}
fa(i,1,n){
fb(j,w,a[i]){
dp[j] = max(dp[j],dp[j-a[i]]+b[i]);
}
}
cout << dp[w] << endl;
return 0;
}
|
