题目描述
题目思路
- 把所有有边相连的点合并在一起，并且维护总体积和总价值
-
把每个连通块看成一个物品，之后做一遍01背包
-
时间复杂度：O(nw)
题目代码
#include
#include
#include
using namespace std;
const int N = 10010;
int n, m, vol;
int v[N], w[N];
int p[N];
int f[N];
int find(int x) // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m >> vol;
for(int i = 1; i > v[i] >> w[i];
for(int i = 1; i > a >> b;
int pa = find(a), pb = find(b);
if(pa != pb)
{
v[pb] += v[pa];
w[pb] += w[pa];
p[pa] = pb;
}
}
// 01背包
for(int i = 1; i = v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[vol] << endl;
return 0;
}
Original: https://www.cnblogs.com/esico/p/16493126.html
Author: esico
Title: AcWing 1252. 搭配购买（并查集+01背包）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619893/
转载文章受原作者版权保护。转载请注明原作者出处！