66 lines
2.2 KiB
C++
66 lines
2.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 10005;
|
||
|
||
int w[N]; //价钱
|
||
int d[N]; //价值(美丽值)
|
||
|
||
int f[N];
|
||
int dp[N];
|
||
|
||
//并查集
|
||
int find(int x) {
|
||
if (f[x] == x) return x;
|
||
return f[x] = find(f[x]);
|
||
}
|
||
|
||
// 【解题思路】
|
||
// 并查集+01背包，都是基本算法╮(╯▽╰)╭
|
||
// 先读进来那一堆价格和价值，然后读进来他们的关系，把有关系的两个合并在一个集合里。
|
||
// 做完并查集了之后把相同代表元素的价格加在一起，价值加在一起，我们就得到了数量<=n的物品，可以做一次01背包，就能求出题目要求的解；
|
||
// 题解：利用并查集把必须一起购买的合并到一起，然后 将一个集合中的物品看做一个物品，变成经典的01背包问题。
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../1414.txt", "r", stdin);
|
||
|
||
int n, m, v; //n，m，v，表示n朵云，m个搭配，Joe有v的钱。
|
||
cin >> n >> m >> v;
|
||
for (int i = 1; i <= n; i++) {
|
||
f[i] = i;//每个人都是自己的爸爸
|
||
cin >> w[i] >> d[i]; //每行wi，di表示i朵云的价钱和价值(美丽值)。
|
||
}
|
||
|
||
//读取它们之间的关系,把有关系的两个合并在一个集合里。
|
||
int x, y;
|
||
while (m--) {
|
||
cin >> x >> y;
|
||
int a = find(x), b = find(y);
|
||
if (a != b) {
|
||
f[b] = a; //a是老大，b里面记录它是a的孩子
|
||
w[a] += w[b]; //它爸爸管理价格,它自己没有资格参加
|
||
d[a] += d[b]; //它爸爸管理价值（美丽值）,它自己没有资格参加
|
||
}
|
||
}
|
||
//
|
||
// cout << "打印w数组进行调试" << endl;
|
||
// for (int i = 1; i <= n; i++) cout << w[i] << " ";
|
||
// cout << endl;
|
||
// cout << "打印d数组进行调试" << endl;
|
||
// for (int i = 1; i <= n; i++) cout << d[i] << " ";
|
||
// cout << endl;
|
||
|
||
//01背包
|
||
for (int i = 1; i <= n; i++) {
|
||
if (f[i] == i) //如果有权利参加的爸爸们！
|
||
for (int j = v; j >= w[i]; j--) {
|
||
dp[j] = max(dp[j], dp[j - w[i]] + d[i]);
|
||
}
|
||
}
|
||
cout << dp[v];
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|