luogu P1455 搭配购买
2024-08-26 00:22:16
题目描述
明天就是母亲节了,电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢?听说在某个网站上有卖云朵的,小朋友们决定一同前往去看看这种神奇的商品,这个店里有n朵云,云朵已经被老板编号为1,2,3,……,n,并且每朵云都有一个价值,但是商店的老板是个很奇怪的人,他会告诉你一些云朵要搭配起来买才卖,也就是说买一朵云则与这朵云有搭配的云都要买,电脑组的你觉得这礼物实在是太新奇了,但是你的钱是有限的,所以你肯定是想用现有的钱买到尽量多价值的云。
输入输出格式
输入格式:
第1行n,m,w,表示n朵云,m个搭配和你现有的钱的数目
第2行至n+1行,每行ci,di表示i朵云的价钱和价值
第n+2至n+1+m ,每行ui,vi表示买ui就必须买vi,同理,如果买vi就必须买ui
输出格式:
一行,表示可以获得的最大价值
输入输出样例
输入样例#1:
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
输出样例#1:
1 思路:看完体面后,第一反应,这不明显的就是,把有搭配的物品全部的价格,价值共加为一个物品,然后将这些物品给做背包不就完事了;
#include<bits/stdc++.h>
using namespace std;
int n,m,money,fa[],w[],v[],f[],MAX;
int find(int x)
{
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&money);
for(int i=;i<=n;i++)
{
fa[i]=i;
scanf("%d%d",&w[i],&v[i]);
}
int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
int g=find(x),h=find(y);
if(g!=h)
{
fa[g]=h;
w[g]+=w[h];w[h]+=w[g];
v[g]+=v[h];v[h]+=v[g];
}
}
for(int i=;i<=n;i++)
{
if(fa[i]==i)
{
for(int j=money;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+v[i]);
MAX=max(MAX,f[j]);
}
}
}
printf("%d",MAX);
}
提交70分
啊哦!貌似加完的忘记清零了,尴尬。
#include<bits/stdc++.h>
using namespace std;
int n,m,money,fa[],w[],v[],f[],MAX;
int find(int x)
{
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&money);
for(int i=;i<=n;i++)
{
fa[i]=i;
scanf("%d%d",&w[i],&v[i]);
}
int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
int g=find(x),h=find(y);
if(g!=h)
{
fa[g]=h;
// w[g]+=w[h];v[g]+=v[h];
w[h]+=w[g];v[h]+=v[g];
// w[h]=0;v[h]=0;
v[g]=;w[g]=;
}
}
for(int i=;i<=n;i++)
{
if(fa[i]==i)
{
for(int j=money;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+v[i]);
MAX=max(MAX,f[j]);
}
}
}
printf("%d",MAX);
}
最新文章
- Java开发环境的配置与Hello World
- iOS10 拍照崩溃问题
- iOS开发——高级篇——如何集成支付宝SDK
- 5332盛照宗 如何获取新技能+c语言学习调查
- C#反射动态调用dll中的方法
- CodeForces 709B Checkpoints (数学,最短路)
- 1-Highcharts环境介绍及配置
- codeforce 606C - Sorting Railway Cars
- requirejs+anjularjs+express框架
- http错误代码含义大全详解
- Oracle 11g透明网关连接Sqlserver 2000
- document.compatMode简介
- 一步一步在Windows中使用MyCat负载均衡 上篇
- 使用selenium时提示:ImportError:No module named selenium
- sql server xp_cmdshell 过程中报错原因
- 20165323《Java程序设计》第九周学习总结
- mysql面试题分组并合并列
- Error: [ng:areq] Argument &#39;LoginCtrl&#39; is not a function, got undefined
- 华为交换机STP 根ID优先级设置
- Linux下多线程下载工具myget