贪心

#include<cstdio>
#include<algorithm>
using namespace std;
int cnt,n,m,F[2000005],c[2000005],last[2000005],G[2000005],E[2000005];
struct node{
int to,next;
}e[2000005];
void add(int a,int b){
e[++cnt].to=b;
e[cnt].next=last[a];
last[a]=cnt;
}
void dfs(int x){
for (int i=last[x]; i; i=e[i].next){
int V=e[i].to;
dfs(V);
}
int cnt=0;
F[x]=c[x];
for (int i=last[x]; i; i=e[i].next){
int V=e[i].to;
F[x]++;
E[++cnt]=F[V]-1;
G[x]+=G[V];
}
sort(E+1,E+cnt+1);
for (int i=1; i<=cnt; i++)
if (F[x]+E[i]<=m){
F[x]+=E[i];
G[x]++;
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) scanf("%d",&c[i]);
for (int i=0; i<n; i++){
int K;
scanf("%d",&K);
while (K--){
int x;
scanf("%d",&x);
add(i+1,x+1);
}
}
dfs(1);
printf("%d\n",G[1]);
return 0;
}

  

最新文章

  1. limux curl命令
  2. 4809 江哥的dp题c
  3. App.js – 用于移动 Web App 开发的 JS 界面库
  4. Jenkins进阶系列之——08Jenkins纳入版本控制
  5. ytu 1938:首字母变大写(水题)
  6. IOS开发之开篇--CocoaPods安装
  7. java小程序整理及排序算法
  8. Linux常用设置
  9. 提取数据表保存为XML文件
  10. VisualBox会造成VPN连接不上问题
  11. 关于cell中添加子视图 复用重叠问题的解决方法
  12. poj 1018 Communication System 枚举 VS 贪心
  13. 神经网络中的BP神经网络和贝叶斯
  14. NFV、DPDK以及部分用户态协议研究
  15. 【转】SHELL variables default value, ${var:-DEFAULT}和${var=DEFAULT}的一点区别
  16. [Swift]LeetCode388. 文件的最长绝对路径 | Longest Absolute File Path
  17. Ansible工具原理一
  18. CSS定位概述
  19. Docker入门5------生产力工具docker-compose
  20. docker启动失败(can&#39;t create unix socket /var/run/docker.sock: is a directory)

热门文章

  1. Spring Task ABC
  2. Java虚拟机内存分配与回收策略
  3. 时间日期相关:Date类、DateFormat类、Calendar类
  4. [转载]&mdash;Health Check Reports Problem: Dependency$ p_timestamp mismatch for VALID objects (文档 ID 781959.1)
  5. Windows Azure 配置Active Directory 主机(2)
  6. 重写strcpy函数,以实现strcpy的功能
  7. mysql数据库备份/恢复
  8. 如何对ABAP SE80 workbench做增强
  9. 在openSUSE 13.1上用gem安装rails无反应: gem install rails
  10. 【转】ios -- ViewController跳转+传值(方式一)