【luogu P1455 搭配购买】 题解
2024-10-22 05:10:18
题目链接:https://www.luogu.org/problemnew/show/P1455
一句话题目做法:并查集合并+01背包
启示:要每次再find一遍。路径压缩会快。因为合并的时候如果是1连3,3连2,4连2,最后也不能保证一步就能连到fa上去。
结果会是fa[2] = fa[3] = fa[4] = 2.
fa[1] = 3.
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = ;
int n,m,money,fa[maxn];//n朵云,m个搭配,w现有钱的数目
int qwqw[maxn],f[maxn],qwqc[maxn],w[maxn],c[maxn];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int unionn(int x, int y)
{ }
int main()
{
scanf("%d%d%d",&n,&m,&money); for(int i = ; i <= n; i++)
fa[i] = i; for(int i = ; i <= n; i++)
{
int fee,d;
scanf("%d%d",&fee,&d);
w[i] = fee; c[i] = d;
}
for(int i = ; i <= m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
int x = find(u);
int y = find(v);
if(x!=y)
fa[y] = x;
} for(int i = ; i <= n; i++)
{
if(fa[i]!=i)
{
c[find(i)] += c[i];
w[find(i)] += w[i];
c[i] = ; w[i] = ;
}
} for(int i = ; i <= n; i++)
for(int v = money; v >= w[i]; v--)
f[v] = max(f[v],f[v-w[i]]+c[i]);
printf("%d",f[money]);
return ;
}
最新文章
- MVC系列——MVC源码学习:打造自己的MVC框架(一:核心原理)
- coreseek 安装及使用方法详解
- ionic overflow:auto失效
- Winform API ";user32.dll";中的函数
- java进程性能分析步骤-超越昨天的自己系列(11)
- Ext Radio 取消选中
- [精华]Hadoop,HBase分布式集群和solr环境搭建
- VLOOKUP和MATCH嵌套以高效引用多列数据
- C语言函数嵌套调用作业总结
- [转载非常好的文章]JLink+GDBServer调试S3C6410裸板的初始化代码 For OK6410开发板
- LeetCode单排日记
- Factors of Factorial AtCoder - 2286 (N的阶乘的因子个数)(数论)
- Mudo C++网络库第七章学习笔记
- 关于Git安装和操作中可能碰到的问题
- Linux中配置别名
- 配置文件springmvc.xml
- Python实现客观赋权法
- 深入理解 Express.js
- webpack css打包为一个css
- ruby中nil?, empty? and blank?
热门文章
- Coursera 机器学习 第8章(上) Unsupervised Learning 学习笔记
- 3、Angular2 Input
- jstl标注标签库
- C# 判断List集合中是否有重复的项
- C# 实现OrderBy按多个字段排序
- 前端如何使用proxyTable和nginx解决跨域问题
- JQuery和html+css实现鼠标点击放烟花
- 菜鸟学习Spring——SpringMVC注解版控制层重定向到控制层
- Android NestedScrollView与RecyclerView嵌套,以及NestedScrollView不会滚动到屏幕顶部解决
- keras 多输出问题