并查集+01背包：1252. 搭配购买

#include<bits/stdc++.h>

using namespace std;

const int N=10000+10;

int v[N],w[N];
int f[N];
int p[N];

int n,m,money;

int find(int x)
{
   
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int main()
{
   
    cin>>n>>m>>money;
    
    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),pb=find(b);
        
        if(pa!=pb)
        {
   
            v[pb]+=v[pa];
            w[pb]+=w[pa];
            p[pa]=pb;
        }
    }
    
    for(int i=1;i<=n;i++)
    {
   
        if(p[i]==i)
        {
   
            for(int j=money;j>=v[i];j--)
            {
   
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
    }
    
    cout<<f[money]<<endl;
    
    return 0;
}

题目里面说了编号从1开始，所以循环变量要从1开始，我就说怎么样例都过不了

首先是并查集处理一下，把搭配的云朵存到一个集合里面，然后维护根节点的价格和价值，只有根节点的价格和价值有意义

然后是用01背包来处理，注意只有选到的云朵是根节点的时候才有意义

01背包模板可以在我的其他博客里面查看