题目链接: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 ;
}

最新文章

  1. MVC系列——MVC源码学习:打造自己的MVC框架(一:核心原理)
  2. coreseek 安装及使用方法详解
  3. ionic overflow:auto失效
  4. Winform API &quot;user32.dll&quot;中的函数
  5. java进程性能分析步骤-超越昨天的自己系列(11)
  6. Ext Radio 取消选中
  7. [精华]Hadoop,HBase分布式集群和solr环境搭建
  8. VLOOKUP和MATCH嵌套以高效引用多列数据
  9. C语言函数嵌套调用作业总结
  10. [转载非常好的文章]JLink+GDBServer调试S3C6410裸板的初始化代码 For OK6410开发板
  11. LeetCode单排日记
  12. Factors of Factorial AtCoder - 2286 (N的阶乘的因子个数)(数论)
  13. Mudo C++网络库第七章学习笔记
  14. 关于Git安装和操作中可能碰到的问题
  15. Linux中配置别名
  16. 配置文件springmvc.xml
  17. Python实现客观赋权法
  18. 深入理解 Express.js
  19. webpack css打包为一个css
  20. ruby中nil?, empty? and blank?

热门文章

  1. Coursera 机器学习 第8章(上) Unsupervised Learning 学习笔记
  2. 3、Angular2 Input
  3. jstl标注标签库
  4. C# 判断List集合中是否有重复的项
  5. C# 实现OrderBy按多个字段排序
  6. 前端如何使用proxyTable和nginx解决跨域问题
  7. JQuery和html+css实现鼠标点击放烟花
  8. 菜鸟学习Spring——SpringMVC注解版控制层重定向到控制层
  9. Android NestedScrollView与RecyclerView嵌套,以及NestedScrollView不会滚动到屏幕顶部解决
  10. keras 多输出问题