首页 > 试题广场 >

【模板】有依赖的背包问题

[编程题]【模板】有依赖的背包问题
  • 热度指数：160 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 n 朵云，云朵已经被老板编号为 1,2,3,...,n，并且每朵云都有一个价值。
\hspace{15pt}但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入描述:
\hspace{15pt}第一行输入三个整数，n,m \left( 1 \leqq n, w \leqq 10^4\right),w\left( 0 \leqq m \leqq 5 \times 10^3\right)，表示有 n 朵云，m 个搭配和你现有的钱的数目。

\hspace{15pt}第二行至 n+1 行，每行有两个整数 c_i,d_i（ 1 \leqq c_i,d_i \leqq 10^3），分别表示第 i 朵云的价钱和价值。

\hspace{15pt}第 n+2 至 n+1+m 行 ，每行有两个整数 u_i,v_i（ 1 \leqq u_i,v_i \leqq n）。表示买第 u_i 朵云就必须买第 v_i 朵云,同理，如果买第 v_i 朵就必须买第 u_i 朵。


输出描述:
\hspace{15pt}输出一行一个正整数，表示可以获得的最大价值。
示例1

输入

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出

1
算法知识视频讲解
添加回答
C++
想当offer收割机的咸鱼很想吃卤蛋头像 想当offer收割机的咸鱼很想吃卤蛋
输入描述说的数据范围有问题，w、m各自的范围没有对应上，写法有问题。
发表于 2025-10-11 15:38:46 回复(0)
提交观点

问题信息

难度：
1条回答 42浏览

热门推荐

相关试题

【模板】有依赖的背包问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号