acwing 1252搭配购买(并查集 + 01背包 )

简介: acwing 1252搭配购买(并查集 + 01背包 )

题目原文

Joe觉得云朵很美,决定去山上的商店买一些云朵。


商店里有 n 朵云,云朵被编号为 1,2,…,n,并且每朵云都有一个价值。


但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。


但是Joe的钱有限,所以他希望买的价值越多越好。


输入格式

第 1 行包含三个整数 n,m,w,表示有 n 朵云,m 个搭配,Joe有 w 的钱。


第 2∼n+1行,每行两个整数 ci,di 表示 i 朵云的价钱和价值。


第 n+2∼n+1+m 行,每行两个整数 ui,vi,表示买 ui 就必须买 vi,同理,如果买 vi 就必须买 ui。


输出格式

一行,表示可以获得的最大价值。

数据范围

1≤n≤10000 ,

0≤m≤5000,

1≤w≤10000,

1≤ci≤5000,

1≤di≤100,

1≤ui,vi≤n

输入样例:

5 3 10

3 10

3 10

3 10

5 100

10 1

1 3

3 2

4 2

输出样例:

1

思路分析

稍微理解一下题意就会发现是dp问题,重点是如何处理题目中加粗部分,即如何将两个物品捆绑起来。其实这种说法是不准确的,这也是造成了我思路错误的原因。最开始的思路就是简单的相加,写完之后发现样例过不了,debug时发现了问题。

正确的思路是并查集+01背包,最基础的并查集就可以实现,然后再用一维数组的01背包计算就行。(虽然写完后又wa了)(在线卑微.jpg)

代码实现

感觉好笨拙的代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10 ;
int n,m,w;
int c1[N],d1[N];
int c[N],d[N];
int root[N];
int f[N];
int find(int x){
    if(root[x] == x) return x;
    else return find(root[x]);
}
void uunion(int a,int b){
    int x = find(a) , y = find(b);
    root[y] = x;
    //c[x] += c[y];
    //d[x] += d[y];
}
int main(){
    cin>>n>>m>>w;
    for(int i = 1; i <= n; i++)
        cin>>c1[i]>>d1[i],root[i] = i;
    while(m--){
        int x,y;
        cin>>x>>y;
        uunion(x,y);
    }
    for(int i = 1; i <= n; i++){
        int u = find(i);
        c[u] += c1[i],d[u] += d1[i];
    }
   // for(int i = 1; i <= n; i++)
     //   cout<<c[i]<<" "<<d[i]<<endl;
    for(int i = 1; i <= n; i++){
         //if(!c[i] || !d[i]) continue;
            if(root[i] == i){
                for(int j = w; j >= c[i]; j--)
                f[j] = max(f[j] , f[j-c[i]]+d[i]);
            }
    }
    cout<<f[w]<<endl;
    return 0;
}

好吧这是个水题。

要补补并查集了(告辞)

目录
相关文章
|
27天前
|
存储 JavaScript 算法
【背包问题】01背包问题和完全背包问题的模板
【背包问题】01背包问题和完全背包问题的模板
|
10天前
|
算法
【洛谷 P1003】[NOIP2011 提高组] 铺地毯 题解(数组+贪心算法)
**NOIP2011 提高组问题:铺地毯** 在第一象限的颁奖典礼场地,有$n$张地毯按编号顺序铺设。需找出覆盖特定点$(x, y)$的最上方地毯编号。输入包括地毯坐标和点坐标,输出地毯编号或-1表示未覆盖。 样例:给定3张地毯,点$(2,2)$被第3张地毯覆盖,输出3;另一样例点$(4,5)$未被覆盖,输出-1。 $30\%$数据$n\leq2$,$50\%$数据坐标$\leq100$,$100\%$数据$n\leq10^4$,坐标$\leq10^5$。 解决方法:从下到上遍历地毯,更新覆盖点的地毯编号。 AC代码略。
6 0
|
2月前
【模板】完全背包和01背包
【模板】完全背包和01背包
24 1
|
2月前
|
人工智能
acwing 5477. 套餐设计
acwing 5477. 套餐设计
|
2月前
|
算法
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
26 0
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
|
2月前
|
算法
算法系列--动态规划--背包问题(2)--01背包拓展题目(上)
算法系列--动态规划--背包问题(2)--01背包拓展题目
26 0
|
7月前
动态规划入门01背包
基本思路: 1.n物品个数,m为背包体积,使用w[i]记录权值,v[i]记录体积,f[i][j]记录选择前i个物体,在不超过j体积下的最优解 最终答案就是f[n][m]; 2.f[i][j]的状态依赖于之前的状态;即f[i[][j]依赖于f[i - 1][j]的状态;也可以理解为所有的状态由f[0][j]推得 f[i][j]的状态不好算出来,但是f[0][j]的状态必定为0,由f[0][j]可以算出f[1][j]的,由f[1][j]又可算出f[2][j]的递推可得出全部。f[1][1] f[2][2] f[3][3]他们每个都减去第i个物品的权值最大值仍不变,最后在加上w[i]即可 即( f[
37 0
|
11月前
|
人工智能 算法 决策智能
动态规划之背包问题(01背包问题、完全背包问题、方案数填满型背包问题)
动态规划之背包问题(01背包问题、完全背包问题、方案数填满型背包问题)
156 1
|
测试技术 容器
动态规划之背包问题——背包三讲(01背包,完全背包,多重背包)(三)
动态规划之背包问题——背包三讲(01背包,完全背包,多重背包)(三)
173 0
动态规划之背包问题——背包三讲(01背包,完全背包,多重背包)(三)