AcWing1252. 搭配购买
思路
先分组 再做01背包
Joe觉得云朵很美，决定去山上的商店买一些云朵。
商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。
但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。
输入格式
第 1 行包含三个整数 n，m，w表示有 n 朵云，m 个搭配，Joe有 w 的钱。
第 2∼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 ≤ n ≤ 10000
0 ≤ m ≤ 5000
1 ≤ w ≤ 10000
1 ≤ c i ≤ 5000
1 ≤ d i ≤ 100
1 ≤ u i , v i ≤ n
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 10010; int f[N], p[N], v[N], w[N]; int n, m, val; int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); } int main() { cin >> n >> m >> val; for (int i = 1;i <= n;++i)p[i] = i; for (int i = 1; i <= n;++i) { cin >> v[i] >> w[i]; } while (m--) { int a, b; cin >> a >> b; int pa = Find(a); int pb = Find(b); if (pa != pb) { v[pb] += v[pa]; w[pb] += w[pa]; p[pa] = p[pb]; } } for (int i = 1;i <= n;++i) { if (p[i] == i) { for (int j = val;j >= v[i];--j) f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[val] << endl; return 0; }
