洛谷 P1455 搭配购买 (并查集+01背包)

传送门

来看题目

看完题目,大意也就是某些云朵是一个集合, 也就是将小云朵们组合成大云朵来买， 那么我们如何将一个集合的数全部加起来呢, 所以我们需要在每次并查集的时候,给祖宗节点加上自己的儿子节点 然后就是操作的问题了 1.我需要找到单个云朵的集合 所以我们需要在并查集之前 定义st数组来判断 2.然后就是我们如何判断已经使用过这个集合了呢？ 当然同理使用标记数组st2,每次进行一遍并查集查询该集合的祖宗节点,如果该祖宗节点被标记就表示这个集合用过了了 3还挺简单的 heihei

#include 
using namespace std;

const int  N = 1e4+10;
const int  maxn = 1e4+10;


int  f[N],p[maxn];


int  n, m, W;
int  v[maxn],w[maxn];
int  v1[maxn],w1[maxn] ;
int  st[maxn] ;

int  idx ;

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

int  main()
{
    cin>>n>>m>>W;
    for(int  i=1; iv[i]>>w[i];

    for(int  i=1; i>a>>b;
        if(a!=b)
        {
            st[a] = 1;
            st[b] = 1;
        }

        int  fa = find(a);
        int  fb = find(b);
        if(fa!=fb)
        {
            p[fa]=fb;
            v[fb] +=v[fa];
            w[fb] +=w[fa];
        }


    }

    for(int  i=1; i