题目传送门(BZOJ)

题解 :

非常明显的贪心

对于一个点,如果要减它的儿子,一定从小的开始减最优,把所有儿子排个序,选最小的直到不能选为止。

排序复杂度要优于O(N\log N)

一开始每个点的儿子siz用了同一个数组存,一直没发现。调个样例竟然上了gdb。

代码 :(BZOJ不资瓷C++11,我shrink_to_fit CE了一发..)

#include <map>#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}const int N = 2000001;struct Edge { int to; Edge *next;}*h[N], e[N];int n, m;vector<int>a[N];inline void Add_Edge(int u, int v) { static int _ = 0; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}int c[N], ans;void dfs(int p) { int cnt = 0; rev(i, p) { dfs(i->to); a[p].push_back(c[i->to]); } sort(a[p].begin(), a[p].end()); c[p] += a[p].size(); cnt = a[p].size(); for(int i = 0; i < cnt; i ++ ) { if(c[p] + a[p][i]-1 <= m) { ans ++; c[p] += a[p][i]-1; } else break; } a[p].clear();}int main() { n = rd(), m = rd(); for(int i = 1; i <= n; i ++ ) c[i] = rd(); for(int i = 1; i <= n; i ++ ) { int x = rd(); for(int j = 1; j <= x; j ++ ) { int u = rd()+1; Add_Edge(i, u); } } dfs(1); printf("%d\n", ans);}