搭配购买

墨蓝 2021-11-13 15:10 317阅读 0赞

[题面][Link 1]

上手发现与01背包仅差一个组合购买，于是愉快并查集+01背包

1 #include <cstdio>
     2 #include <iostream>
     3 #include <algorithm>
     4 using namespace std;
     5 
     6 int father[20001],c[20001],w[20001],f[20001];
     7 int n,m,k,x,y;
     8 
     9 int find(int x) 
    10 {
    11     return x==father[x]?x:father[x]=find(father[x]);
    12 }
    13 
    14 int main()
    15 {
    16     scanf("%d%d%d",&n,&m,&k);
    17     for (int i=1;i<=n;i++)
    18     {
    19         scanf("%d%d",&w[i],&c[i]);
    20         father[i]=i;  //初始化
    21     } 
    22     for (int i=1;i<=m;i++)
    23     {
    24         scanf("%d%d",&x,&y);
    25         if (find(x)!=find(y)) father[find(y)]=find(x);  
    26     }
    27     for (int i=1;i<=n;i++)
    28      if (father[i]!=i) 
    29      {
    30         c[find(i)]+=c[i];
    31         w[find(i)]+=w[i]; 
    32         c[i]=w[i]=0; 
    33      }
    34     for (int i=1;i<=n;i++)
    35      for (int j=k;j>=w[i];j--)
    36       f[j]=max(f[j],f[j-w[i]]+c[i]); 
    37     printf("%d\n",f[k]);
    38     return 0;
    39 }

转载于:https://www.cnblogs.com/ainiyuling/p/11136987.html

[Link 1]: https://www.luogu.org/problemnew/show/P1455

发表评论取消回复

表情：

评论列表（有 0 条评论，317人围观）

还没有评论，来说两句吧...

相关阅读

相关快速购买系统

测试网址：[https://www.boyuan.com/api/a/plugin/shop.php?username=boyuan][https_www.boyuan.com

- 日理万妓/ 2023年08月17日 17:27/ 0 赞/ 95 阅读

相关 Redis 购买经验

选择集群的双分布内网吞吐量高很多 ![20200918154434276.png][] 简单的使用 <table> <tbody> <tr> <td

布满荆棘的人生/ 2022年12月08日 05:28/ 0 赞/ 185 阅读

相关 Ajax 搭配 Promise 封装

简述 Ajax（Asynchronous JavaScript And XML） Promise JavaScript

客官°小女子只卖身不卖艺/ 2022年05月25日 02:26/ 0 赞/ 258 阅读

相关 ElasticSearch环境搭配

1：单机环境 [http://www.elasticsearch.org/download/][http_www.elasticsearch.org_download]

蔚落/ 2022年05月14日 23:16/ 0 赞/ 209 阅读

相关 SVN服务器搭配说明

SVN服务器搭配说明环境 OS：Windows XP SP2 Web：Apache 2.2.6 SVN：svn-win32-1.4.6 一、准备工作 1

ゞ浴缸里的玫瑰/ 2022年03月11日 07:15/ 0 赞/ 188 阅读

相关 Logback 为日志配置颜色搭配（彩色搭配日志-搭配方案）

Logback 为日志配置颜色搭配（彩色搭配日志-搭配方案）截图： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_

末蓝、/ 2022年02月26日 04:00/ 0 赞/ 950 阅读

相关 notpad++ 搭配 gcc

notpad++ 搭配 gcc GCC 是 GNU 编译器套装的简称（GNU Compiler Collection），一套编程语言编译器，以 GPL 及 LGPL 许可

缺乏、安全感/ 2022年01月09日 11:45/ 0 赞/ 302 阅读

相关搭配购买

[题面][Link 1] 上手发现与01背包仅差一个组合购买，于是愉快并查集+01背包 1 include <cstdio> 2 include <ios

墨蓝/ 2021年11月13日 15:10/ 0 赞/ 318 阅读

相关购买须知！必读！

> 非常感谢！真的非常感谢大家的认可，这，毕竟是一个付费产品，虽然价格不贵，但毕竟是钱，你们肯付费支持，不管怎样，庆哥真诚的说声“感谢”！今后一起加油！非常重要：订阅后一

向右看齐/ 2021年09月08日 11:18/ 0 赞/ 381 阅读

相关 uview颜色搭配

一、字体颜色 > uview 分别提炼了4种用于文字颜色，分别是：主要文字、常规文字、次要文字、占位文字颜色。主要文字颜色一般用于内容的标题等，如新闻列表的标题 > 常

╰半夏微凉°/ 2021年07月25日 20:02/ 0 赞/ 1553 阅读