【bzoj4027】[HEOI2015]兔子与樱花

时间:2022-10-28 15:19:48

题目描述

很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接,我们可以把它看成一个有根树结构,其中0号节点是根节点。这个树的每个节点上都会有一些樱花,其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m,即son(i) + c_i <= m,其中son(i)表示i的儿子的个数,如果i为叶子节点,则son(i) = 0

现在兔子们觉得樱花树上节点太多,希望去掉一些节点。当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除,那么就会继续向上连接,直到第一个没有被删除的节点为止。
现在兔子们希望计算在不违背最大载重的情况下,最多能删除多少节点。
注意根节点不能被删除,被删除的节点不被计入载重。

输入

第一行输入两个正整数,n和m分别表示节点个数和最大载重

第二行n个整数c_i,表示第i个节点上的樱花个数

接下来n行,每行第一个数k_i表示这个节点的儿子个数,接下来k_i个整数表示这个节点儿子的编号

输出

一行一个整数,表示最多能删除多少节点。

样例输入

10 4
0 2 2 2 4 1 0 4 1 1
3 6 2 3
1 9
1 8
1 1
0
0
2 7 4
0
1 5
0

样例输出

4

提示

对于100%的数据,1 <= n <= 2000000, 1 <= m <= 100000, 0 <= c_i <= 1000

数据保证初始时,每个节点樱花数与儿子节点个数之和大于0且不超过m


题解

树形dp+贪心

每次删除选定节点后,增加的重量为(选定节点的子节点数目+选定节点的樱花数)-1,

那么我们完全可以讲每个节点的重量看作子节点数目+樱花数。

于是就有贪心策略:优先选择重量小的子节点删除,否则若选择其它子节点,那么这个节点删掉的子节点不会增多,而且这个节点的重量会比贪心方案大,影响后面的处理。

先更新子节点的重量,并从小到大排序,根据贪心策略优先选择重量小的,判断能否去掉,若能去掉则更新当前节点的重量。

时间复杂度为O(nlogn),但常数较小,可以过。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> son[2000001];
int c[2000001] , m , ans;
bool cmp(int a , int b)
{
return c[a] < c[b];
}
void dp(int x)
{
int i;
for(i = 0 ; i < (int)son[x].size() ; i ++ )
dp(son[x][i]);
sort(son[x].begin() , son[x].end() , cmp);
c[x] += son[x].size();
for(i = 0 ; i < (int)son[x].size() ; i ++ )
{
if(c[x] + c[son[x][i]] - 1 <= m)
{
c[x] += c[son[x][i]] - 1;
ans ++ ;
}
else
break;
}
}
int main()
{
int n , i , k , x;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ )
scanf("%d" , &c[i]);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%d" , &k);
while(k -- )
{
scanf("%d" , &x);
son[i].push_back(x + 1);
}
}
dp(1);
printf("%d\n" , ans);
return 0;
}

【bzoj4027】[HEOI2015]兔子与樱花的更多相关文章

  1. BZOJ4027&colon; &lbrack;HEOI2015&rsqb;兔子与樱花 贪心

    觉得是贪心,但是一开始不太肯定...然后就A了 一个点对它的父亲的贡献就是自己的权值加儿子的个数 #include<bits/stdc++.h> using namespace std; ...

  2. bzoj4027 &lbrack;HEOI2015&rsqb;兔子与樱花 树上贪心

    [HEOI2015]兔子与樱花 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1320  Solved: 762[Submit][Status][Di ...

  3. &lbrack;bzoj4027&rsqb;&lbrack;HEOI2015&rsqb;兔子与樱花&lowbar;贪心&lowbar;树形dp

    兔子与樱花 bzoj-4027 HEOI-2015 题目大意:每个点有c[i]朵樱花,有一个称重m, son[i]+c[i]<=m.如果删除一个节点,这个节点的樱花或移动到它的祖先中深度最大的, ...

  4. &lbrack;BZOJ4027&rsqb;&lbrack;HEOI2015&rsqb; 兔子与樱花

    Description 很久很久之前,森林里住着一群兔子.有一天,兔子们突然决定要去看樱花.兔子们所在森林里的樱花树很特殊.樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接 ...

  5. &lbrack;BZOJ4027&rsqb;&lbrack;HEOI2015&rsqb;兔子与樱花 树形dp

    Description 很久很久之前,森林里住着一群兔子.有一天,兔子们突然决定要去看樱花.兔子们所在森林里的樱花树很特殊.樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接 ...

  6. &lbrack;bzoj4027&rsqb;&lbrack;HEOI2015&rsqb;&lbrack;兔子与樱花&rsqb; &lpar;树形dp思想&plus;玄学贪心&rpar;

    Description 很久很久之前,森林里住着一群兔子.有一天,兔子们突然决定要去看樱花.兔子们所在森林里的樱花树很特殊.樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接 ...

  7. BZOJ4027 HEOI2015兔子与樱花(贪心)

    首先显然地如果某个点超过了最大负载,删掉它仍然是不合法的.删除某个点当前只会对其父亲产生影响,同一个节点的儿子显然应该按代价从小到大删.考虑如果删掉某个点之后他的父亲不能再删了,我们损失了父亲这个点, ...

  8. 【BZOJ4027】&lbrack;HEOI2015&rsqb;兔子与樱花 贪心

    [BZOJ4027][HEOI2015]兔子与樱花 Description 很久很久之前,森林里住着一群兔子.有一天,兔子们突然决定要去看樱花.兔子们所在森林里的樱花树很特殊.樱花树由n个树枝分叉点组 ...

  9. B20J&lowbar;4027&lowbar;&lbrack;HEOI2015&rsqb;兔子与樱花&lowbar;树形DP

    B20J_4027_[HEOI2015]兔子与樱花_树形DP 题意: 很久很久之前,森林里住着一群兔子.有一天,兔子们突然决定要去看樱花.兔子们所在森林里的樱花树很特殊.樱花树由n个树枝分叉点组成,编 ...

  10. 【BZOJ4027】兔子与樱花(贪心)

    [BZOJ4027]兔子与樱花(贪心) 题面 BZOJ 洛谷 题解 很直观的一个感受就是对于每个节点, 考虑它的所有儿子,如果能删就删. 那么我们把所有儿子按照给删去后给父亲\(c[i]\)的贡献从小 ...

随机推荐

  1. 利用C&num; Winform做Windows系统任务栏

    最近公司做一个考试系统,需要一个答题栏,要求:占用屏幕上方一部分区域,而且始终置顶,当其他窗口最大化时"答题栏"始终置前并且不遮挡最大化窗口的任何部分!就像windows任务栏一样 ...

  2. 如何使用android百度地图离线地图

    1.首先把离线地图放在android工程下的assets里面. 注意:建议离线地图下载通过百度地图APIDEMO去下载,因为到官网上下载的离线地图文件格式不一样,APIDEMO的格式是.dat,而官网 ...

  3. SQL Queries from Transactional Plugin Pipeline

    Sometimes the LINQ, Query Expressions or Fetch just doesn't give you the ability to quickly query yo ...

  4. Httpclient请求数据

    package com.baidu.myutils; import java.io.IOException; import org.apache.http.HttpEntity; import org ...

  5. PetaPoco 访问SQL SERVER 存储过程

    博客园有篇文章<小巧方便的ORM类库——PetaPoco>  介绍了PetaPoco调用存储过程: //调用存储过程 db.Execute("exec procSomeHandl ...

  6. 网络编程-socket

    本节内容: 一:TCP/IP:Transmission Control Protocol/Internet Protocol 传输控制协议/因特网互联协议.即通讯协议.是主机接入互联网以及互联网中两台 ...

  7. C&num;中的Collections命名空间

    System.Collections命名空间包含可使用的集合类和相关的接口. 该命名空间下的.NET非泛型集合类如下所示: — System.Collections.ArrayList:数组集合类,使 ...

  8. 基于java的InputStream&period;read&lpar;byte&lbrack;&rsqb; b&comma;int off&comma;int len&rpar;算法学习

    public int read(byte[] b, int off, int len) throws IOException 将输入流中最多 len 个数据字节读入字节数组.尝试读取多达 len 字节 ...

  9. 马赛克算法及iOS代码实现

    之前做了一下相关涂鸦的东西,发现图片处理挺好玩的,就先讲讲马赛克的实现吧. 放大马赛克图片可以看到,可以看到一个个单色的小正方形.所以马赛克其实也就是把某一点的色值填充了它一定范围内的一个正方形,这样 ...

  10. fabric&period;js和高级画板

    本文介绍fabric.js框架使用,以及使用fabricjs打造一个高级画板程序. 高级画板功能介绍 全局绘制颜色选择 护眼模式.网格模式切换 *绘制 画箭头 画直线 画虚线 画圆/椭圆/矩形/直角 ...