当前位置: 首页 > news >正文

搭配购买——并查集+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

解析:

搭配的都要买,可以理解成将有关系的都放在一起,相当一个物品,要买一起买。

这样就可以转换成01背包问题,每个物品只能购买一次,在有限的钱的情况下,让买的物品的价值尽可能的大。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int p[N];
int v[N],w[N];
int v1[N],w1[N];
int f[N];
bool vis[N];
int find(int x)
{if (x!=p[x]) p[x]=find(p[x]);return p[x];
}
signed main()
{int n,m,k;cin>>n>>m>>k;for (int i=1;i<=n;i++) p[i]=i;for (int i=1;i<=n;i++) cin>>v[i]>>w[i];for (int i=0;i<m;i++){int a,b;cin>>a>>b;int x=find(a),y=find(b);if (x!=y){v[y] +=v[x];w[y] +=w[x];p[x]=y;}}int cnt=0;for (int i=1;i<=n;i++){int x=find(i);if (!vis[x]){cnt++;v1[cnt]=v[x];w1[cnt]=w[x];vis[x]=1;}}for (int i=1;i<=cnt;i++)       //01背包最简化  //模板for (int j=k;j>=v1[i];j--)f[j]=max(f[j],f[j-v1[i]]+w1[i]);cout<<f[k];return 0;
}//发现可以简化一下代码,不需要开新的数组记录每个“新的物品”的价值和代价。#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int p[N];
int v[N],w[N];
int f[N];
int find(int x)
{if (x!=p[x]) p[x]=find(p[x]);return p[x];
}
signed main()
{int n,m,k;cin>>n>>m>>k;for (int i=1;i<=n;i++) p[i]=i;for (int i=1;i<=n;i++) cin>>v[i]>>w[i];for (int i=0;i<m;i++){int a,b;cin>>a>>b;int x=find(a),y=find(b);if (x!=y){v[y] +=v[x];w[y] +=w[x];p[x]=y;}}for (int i=1;i<=n;i++)       //01背包最简化  //模板if (p[i]==i)                 //每个集合的根节点{for (int j=k;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);}cout<<f[k];return 0;
}

相关文章:

搭配购买——并查集+01背包

Joe觉得云朵很美&#xff0c;决定去山上的商店买一些云朵。 商店里有 n 朵云&#xff0c;云朵被编号为 1,2,…,n&#xff0c;并且每朵云都有一个价值。但是商店老板跟他说&#xff0c;一些云朵要搭配来买才好&#xff0c;所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有…...

JVM调优指令参数

常用命令查找文档站点&#xff1a;https://docs.oracle.com/javase/8/docs/technotes/tools/unix/index.html -XX:PrintFlagsInitial 输出所有参数的名称和默认值&#xff0c;默认不包括Diagnostic和Experimental的参数。可以配合 -XX:UnlockDiagnosticVMOptions和-XX:UnlockEx…...

数据结构入门 — 队列

本文属于数据结构专栏文章&#xff0c;适合数据结构入门者学习&#xff0c;涵盖数据结构基础的知识和内容体系&#xff0c;文章在介绍数据结构时会配合上动图演示&#xff0c;方便初学者在学习数据结构时理解和学习&#xff0c;了解数据结构系列专栏点击下方链接。 博客主页&am…...

MongoDB - 安装

一、Docker安装MongoDB 1. 安装 安装版本: 7.0.0 docker run -itd --name mongodb -v C:\\data\\mongodb\\data:/data/db -p 27017:27017 mongo:7.0.0 --auth-v: 将容器目录/data/db映射到本地C:\\data\\mongodb\\data目录&#xff0c;防止容器删除数据丢失-p: 端口映射--aut…...

Qt应用开发(基础篇)——颜色选择器 QColorDialog

一、前言 QColorDialog类继承于QDialog&#xff0c;是一个设计用来选择颜色的对话框部件。 对话框窗口 QDialog QColorDialog颜色选择器一般用来让用户选择颜色&#xff0c;比如画图工具中选择画笔的颜色、刷子的颜色等。你可以使用静态函数QColorDialog::getColor()直接显示对…...

vscode 清除全部的console.log

在放页面的大文件夹view上面右键点击在文件夹中查找 console.log.*$ 注意&#xff1a;要选择使用正则匹配 替换为 " " (空字符串)...

UG\NX CAM二次开发 插入工序 UF_OPER_create

文章作者:代工 来源网站:NX CAM二次开发专栏 简介: UG\NX CAM二次开发 插入工序 UF_OPER_create 效果: 代码: void MyClass::do_it() {tag_t setup_tag=NULL_TAG;UF_SETUP_ask_setup(&setup_tag);if (setup_tag==NULL_TAG){uc1601("请先初始化加工环境…...

C++指针、指针函数、函数指针、类指针

1、指针变量 #include <iostream>using namespace std;int main () {int var 20; // 实际变量的声明int *ip; // 指针变量的声明ip &var; // 在指针变量中存储 var 的地址cout << "Value of var variable: ";cout << var …...

图:最短路径问题(BFS算法,Dijkstra算法,Floyd算法)

1 .单源最短路径 1.BFS算法(无权图) 使用广度优先遍历实现一个顶点到达其他所有顶点的最短路径。 注:无权图可以视为一种特殊的带权图&#xff0c;只是每条边的权值都为1。 1.算法思路&#xff1a; 定义一个数组存储每个结点与当前的结点的最短距离&#xff0c;定义一个数组…...

栈和队列篇

目录 一、栈 1.栈的概念及结构 1.1栈的概念 1.2栈的结构示意图 2.栈的实现 2.1支持动态增长的栈的结构 2.2压栈&#xff08;入栈&#xff09; 2.3出栈 2.4支持动态增长的栈的代码实现 二、队列 1.队列的概念及结构 1.1队列的概念 1.2队列的结构示意图 2.队列的实…...

分享一个vue-slot插槽使用场景

需求再现 <el-table-column align"center" label"状态" prop"mitStatus" show-overflow-tooltip />在这里&#xff0c;我想对于状态进行一个三目判断&#xff0c;如果为0那就是进行中&#xff0c;否则就是已完成&#xff0c;期初我是这样写…...

Qt应用开发(基础篇)——进度对话框 QProgressDialog

一、前言 QProgressDialog类继承于QDialog&#xff0c;是Qt设计用来反馈进度的对话框。 对话框QDialog QProgressDialog提供了一个进度条&#xff0c;表示当前程序的某操作的执行进度&#xff0c;让用户知道操作依旧在激活状态&#xff0c;配合按钮&#xff0c;用户就可以随时终…...

基于SpringBoot2的后台业务管理系统

概述 SpringBoot-Plus 是一个适合大系统拆分成小系统的架构&#xff0c;java快速开发平台&#xff0c;或者是一个微服务系统。其中加入了Thymeleaf数据模板语言代替了之前的JSP页面方式。页面展示采用Layui前端框架&#xff0c;包含了用户管理&#xff0c;角色管理&#xff0c…...

Jmeter(三十):并发测试(设置集合点)

集合点:让所有请求在不满足条件的时候处于等待状态。 如:我集合点设置为50,那么不满足50个请求的时候,这些请求都会集合在一起,处于等待状态,当达到50的时候,就一起执行。从而达到并发的效果。 那么Jmeter中可以通过同步定时器 Synchronizing Timer 来完成。 Number …...

Flink的checkpoint是怎么实现的?

分析&回答 Checkpoint介绍 Checkpoint容错机制是Flink可靠性的基石,可以保证Flink集群在某个算子因为某些原因(如 异常退出)出现故障时,能够将整个应用流图的状态恢复到故障之前的某一状态,保证应用流图状态的一致性。Flink的Checkpoint机制原理来自“Chandy-Lamport alg…...

ubuntu上安装nginx

这篇文章主要介绍怎么在ubuntu上安装nginx服务器&#xff0c;并进行一些简单的配置。 第一步&#xff1a;准备好一台ubuntu操作系统的虚拟机 注意&#xff1a;如果你还没有安装好ubuntu&#xff0c;个人推荐阅读以下文章完成unbutu安装&#xff0c;vm的版本不用刻意安装文章中…...

9. 微积分 - 导数

文章目录 导数求导实例代码演示:迭代法求解二次函数最小值阶Hi, 大家好。我是茶桁。 我们终于结束了极限和连续的折磨,开启了新的篇章。 不过不要以为我们后面的就会很容易,只是相对来说, 没有那么绕而已。 那么,我们今天开始学习「导数」。 导数 在之前的导论,也就是…...

滑动窗口系列1-达标子数组

#达标子数组# 求达标子数组的数量 * 题目&#xff1a;给定一个数组&#xff0c;求满足子数组中最大值-最小值小于等于某个数的子数组的数量 * 例如[0,1,2,3]中求子数组中最大值-最小值小于等于 2的子数组的数量 * 结果为9,因为满足条件的只有[0,0] [0,1] [0,2] [1,1] [1,2] [1…...

电视显示技术及价格成本对比(2023年)

版权声明&#xff1a;本文为博主原创文章&#xff0c;遵循 CC 4.0 BY-SA 版权协议&#xff0c;转载请附上原文出处链接和本声明。 本文链接&#xff1a;https://blog.csdn.net/zaibeijixing/article/details/132461068 ———————————————— 截止到2023年&#xff…...

浅谈 Pytest+HttpRunner 如何展开接口测试!

软件测试有多种多样的方法和技术&#xff0c;可以从不同角度对它们进行分类。其中&#xff0c;根据软件生命周期&#xff0c;针对不同的测试对象与目标&#xff0c;可将测试过程分为 4 个阶段&#xff1a;单元测试、集成测试、系统测试和验收测试。本文着重介绍了如何借用 pyte…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...