不一定要最后合并集合吧

对的 不需要 不影响

怎么没影响，这是合并成一个新的云了，只考虑根节点就行啊

自己试一试，实践出真知

这样复杂度不是 n^2么，不会超时啊

请问大佬
for(int i = m; i >= 0; i – )
for(int j = 1; j <= n; j ++ )
if(p[j] == j && cost[j] <= i) {
f[i] = Math.max(f[i], f[i - cost[j]] + v[j]);
res = Math.max(res, f[i]);
}
我先枚举的体积为什么错了牙
改成先枚举物品就对了

01背包能空间优化是因为每次只用上一层的数据
先枚举体积肯定有问题

 while(m--){
        int a,b;
        cin >> a >> b;
        int pa=find(a);int pb=find(b);
        if(pa!=pb){
            w[pb]+=w[pa];
            v[pb]+=v[pa];
            p[pa]=p[pb];//注意这里一定要最后合并集合
        }
    }

这里的合并放在前面和后面没啥区别吧

没区别,只要在大括号里面合并都行，因为不会影响w,v的值

### 我也是这么认为的

大佬，我用二维写，好像不太能通过呀

for (int i = 1; i <= n; i ++ )
        if (p[i] == i)
        for(int j=1;j<=sum;j++){
            f[i][j] = f[i-1][j];
            if(v[i]<=j){
                f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i])
            }
        }    
cout<<f[n][sum];

主要是因为f[i]不一定是依赖i - 1的，需要维护一个last，表示上一次更新的是哪个f[i]然后状态转移方程就是f[i][j] = max(f[i][j[], f[last][j - v[i]] + w[i])，最后别忘了把last更新成i就可以了。

这道题好像优化成一维的更方便

请问二维咋写

二维会mle 全局数组最多开到1e7(稍微多一点)

大佬我思路和你一样呀，就是写的比较麻烦，不知道哪里错了，大佬们可以指点一波吗，代码比较丑陋

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

const int N = 10005;
const int M = 5005;
int fa[N];

int find(int x)
{
    if(x != fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}
void Union(int x, int y)
{
    int x_root = find(x);
    int y_root = find(y);
    if(x_root != y_root)
    {
        fa[x_root] = y_root;
    }
}
int main()
{
    int n = 0;
    int m = 0;
    int v = 0;
    cin >> n >> m >> v;
    vector<int> sums(n + 1);
    vector<int> values(n + 1);
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    for(int i = 1; i <= n; i++)
    {
        cin >> sums[i] ;
        cin >> values[i] ;
    }
    //vp[] 价钱  价值
    while(m--)
    {
        int a = 0;
        int b = 0;
        cin >> a >> b;
        if(find(a) != find(b))
        {
            Union(a,b); // a的节点指向b，b是根据点
            sums[b] += sums[a];
            values[b] += values[a];
        }
    }
    /*
    for(int i = 1 ; i <= n; i++)
    {
        cout << fa[i] <<endl;
    }
    */
    set<int> s;
    for(int i = 1; i <= n; i++)
    {
        if(fa[i] == i)
            s.insert(i);
        else
            s.insert(find(i));
    }
    //sums[i] 是价格
    //values[i] 是价值
    int k  = s.size() + 1;
    int c[k];
    int d[k];
    int index1 = 1;
    int index2 = 1;
    for(auto e: s)
    {
        c[index1++] = sums[e] ;
        d[index2++] = values[e];
    }
    int f[v + 1];
    memset(f,0,sizeof f);
    for(int i = 1; i <= k - 1 ; i++)
    {
        for(int j = v; j >= c[i]; j--)
        {
            f[j] = max(f[j],f[j - c[i]] + d[i]);
        }
    }
    cout << f[v] << endl;
}

你合并的代码有点问题吧，是合并ab所在的集合