我们可以把搭配的那些云当作一个一个的连通块，然后把这些连通快当成每个物体

比如，本题就是两个连通块

当我们做好连通块儿的时候，我们分析一下01背包

step1 分析状态表示 f[i][j]表示 从1到i个物品选出价格不超过j的最大价值

step2:推导状态转移方程

初始化，我们还是全部初始化为0就行了

最后答案就在f[cnt][p]里

最后我们优化成一维

好的我们来实现一下代码吧

#include <iostream>
#include <vector>
using namespace std;
int n, m, p;
const int N = 1e4 + 10;
int w[N], v[N];
bool st[N];
int cnt;
vector<int> edges[N];
int vv[N], ww[N];//vv代表价值，ww代表价格 
int f[N];
void dfs(int i)
{st[i] = true;vv[cnt] += v[i];ww[cnt] += w[i];for (auto& e : edges[i]){if (!st[e]){dfs(e);}}
}
int main()
{cin >> n >> m >> p;for (int i = 1; i <= n; i++){cin >> w[i] >> v[i];}//构建图 for (int i = 1; i <= m; i++){int x, y; cin >> x >> y;edges[x].push_back(y);edges[y].push_back(x);}//dfs合并连通块 for (int i = 1; i <= n; i++){if (!st[i]){cnt++;dfs(i);}}//01背包for (int i = 1; i <= cnt; i++){for (int j = p; j >= ww[i]; j--){f[j] = max(f[j], f[j - ww[i]] + vv[i]);}}cout << f[p] << endl;return 0;
}