算法分析

并查集

• 1、由于云朵的相关性，有关联的云朵都得一起买，即把有关联的云朵看成一个集合

• 2、记录集合的大小，需要将其价格和价值绑定在根结点中，即根结点的价格和价值代表着整个集合，把每个集合看成一个物品，且每个物品只能取一次，因此转换成了01背包求最大价值问题

时间复杂度$O(nm)$

并查集操作接近$O(1)$

参考文献

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int N = 10010;
    static int n,m,vol;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[] p = new int[N];
    static int[] f = new int[N];
    static int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        vol = Integer.parseInt(s1[2]);
        for(int i = 1;i <= n;i ++) p[i] = i;

        for(int i = 1;i <= n;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s2[0]);
            w[i] = Integer.parseInt(s2[1]);
        }
        while(m -- > 0)
        {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            int pa = find(a);
            int pb = find(b);

            if(pa != pb)
            {
                v[pb] += v[pa];
                w[pb] += w[pa];
                p[pa] = pb;
            }
        }

        //01 背包
        for(int i = 1;i <= n;i ++)
            if(p[i] == i)
                for(int j = vol;j >= v[i];j --)
                    f[j] = Math.max(f[j], f[j - v[i]] + w[i]);

        System.out.println(f[vol]);
    }
}