P4572题解

· · 题解

虽然但是这是蒟蒻第一次写灰题

题意：

军队从树的根部开始，

有可能花费一个小时进入任意一个子节点，

必须有人能够激活可能进入的子节点的魔法（不能重复），
当军队进入选中的子节点时，上一次用的人可以立刻到可能进入的任意子节点，如果人手不够可以增加。

听不懂？往下看↓

思路：

图论不会还不能画图吗？

首先从根节点开始进入：


那么可能进入的子节点就是 2 , 3

那么马上就会有人到 2 , 3 两个点，
因此 ans = 2
伏地魔：先收了 2 下面的建筑，收的多才能鼓舞士气
所以此时伏地魔大军来到了 2 ,
霍格沃茨的人反应很快，立刻到了接下来的可能的结点：
因为求的是至少，那么考虑最差情况!!!

然后凤凰社的这堆祸害OI的人奆佬就屁颠屁颠地跑到了 4 , 5 , 6 的点。
因此 ans = 3

这个过程写个深搜就好了 

void dfs(int f, int idx, int tot, int time){
    /*
    **  当大军走到idx这个点的时候，必须修建好idx的子节点 
    **  tot需要记录idx的子节点子节点的个数,time即时间变化
    **  计算此时需要的人数并与原res比较 
    */

    tot+=v[idx].size(); //也是参考了楼顶才发现要+=而不是=
    res=max(res,(int)ceil(tot/time));
    for(int i=0;i<v[idx].size();i++){//枚举所有子节点 
        if(v[i][idx]!=f) dfs(idx,v[i][idx],tot,time+1);  //蒟蒻这里写反了然后全RE,,
    }
}