BZOJ4027 HEOI2015兔子与樱花（贪心）

　　首先显然地如果某个点超过了最大负载，删掉它仍然是不合法的。删除某个点当前只会对其父亲产生影响，同一个节点的儿子显然应该按代价从小到大删。考虑如果删掉某个点之后他的父亲不能再删了，我们损失了父亲这个点，但不会对其他点产生任何影响；而若删掉父亲，其儿子节点中能够删除的节点肯定会更少，且会对爷爷造成负面影响。所以我们贪心的自底向下删点就好了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 2000010

int n,m,a[N],s[N],t,ans;

vector<int> son[N];

bool cmp(const int&x,const int&y)

{

    return a[x]<a[y];

}

void dfs(int k)

{

    int cnt=;

    for (int i=;i<s[k];i++) dfs(son[k][i]);

    sort(son[k].begin(),son[k].end(),cmp);

    for (int i=;i<s[k];i++)

    if (a[k]+a[son[k][i]]-<=m) a[k]+=a[son[k][i]]-,ans++;

    else break;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4027.in","r",stdin);

    freopen("bzoj4027.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<=n;i++)

    {

        a[i]+=s[i]=read();

        for (int j=;j<=s[i];j++) son[i].push_back(read()+);

    }

    dfs();

    cout<<ans;

    return ;

}

秒客网

BZOJ4027 HEOI2015兔子与樱花（贪心）

相关文章