洛谷P1455 搭配购买

@Pelom  October 27, 2019

题意

有$n$个物品,$m$个关系,有关系的物品必须一起购买,求最大价值

数据范围:$n,w \le 10000,m \le 5000$

题解

用并查集把有关系的物品合并成$1$个,再用$01$背包即可

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10000+10;
int n,m,w,u,v;
int c[N],d[N],fa[N],dp[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&c[i],&d[i]);
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        if((u=find(u))==(v=find(v)))
            continue;
        fa[u]=v;
        c[v]+=c[u];
        d[v]+=d[u];
    }
    for(int i=1;i<=n;i++)
        if(fa[i]==i)
            for(int j=w;j>=c[i];j--)
                dp[j]=max(dp[j],dp[j-c[i]]+d[i]);
    printf("%d",dp[w]);
    return 0;
}

添加新评论