AcWing 1252. 搭配购买---Java
原题链接
简单
作者:
夏日的小提琴
,
2021-12-17 16:19:44
,
所有人可见
,
阅读 252
import java.io.*;
public class Main {
static int n, m, val;
static int[] v, w;//每个云朵的体积和价值
static int[] p;//每个云朵的父节点
static int[] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
val = Integer.parseInt(str[2]);
v = new int[n + 1];
w = new int[n + 1];
p = new int[n + 1];
f = new int[val + 1];
for (int i = 1; i <= n; i++) {
String[] str1 = reader.readLine().split(" ");
v[i] = Integer.parseInt(str1[0]);
w[i] = Integer.parseInt(str1[1]);
p[i] = i;//初始每个云朵的父节点就是自己
}
while (m-- > 0) {
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
if (find(a) != find(b)) {//则需要将a集合接到b集合
v[find(b)] += v[find(a)];//更新b集合的总体积大小
w[find(b)] += w[find(a)];//更新b集合的总价值大小
p[find(a)] = find(b);//将a集合挂到b集合
}
}
//01背包操作,相当于把每个集合看成不同物品,其中,每个集合的根节点保存着物品的体积和价值
for (int i = 1; i <= n; i++) {//遍历物品
if (p[i] == i) {//只需要对每个集合的根节点进行选择即可
for (int j = val; j >= v[i]; j--) {
f[j] = Math.max(f[j], w[i] + f[j - v[i]]);//注意这里只能用一维的f去求,因为这里物品不是连续的,f[i][j] = f[i - 1][j]则就会出错
}
/*for (int j = 0; j <= val; j++) {//遍历已有的总体积,看能装最大多少价值
if (v[i] > j) {//只能不选
f[i][j] = f[i - 1][j];
} else {
f[i][j] = Math.max(f[i - 1][j], w[i] + f[i - 1][j - v[i]]);//选与不选第i件物品中计算最大价值
}
}*/
}
}
writer.write(f[val] + "");
writer.flush();
writer.close();
reader.close();
}
//并查集核心代码,查找根节点 + 路径压缩
public static int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}