当前位置: 首页 > 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…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

使用python进行图像处理—图像滤波(5)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...

C#中用于控制自定义特性(Attribute)

我们来详细解释一下 [AttributeUsage(AttributeTargets.Class, AllowMultiple false, Inherited false)] 这个 C# 属性。 在 C# 中&#xff0c;Attribute&#xff08;特性&#xff09;是一种用于向程序元素&#xff08;如类、方法、属性等&#xff09;添加元数据的机制。Attr…...