题解 P7320 【[JSOI2013] 哈利波特与死亡圣器】

L_sdcs · 2021-02-02 09:27:29 · 题解

题目传送门

题目大意

由于本蒟蒻语文能力有限，表达不出来，请自行查看题目，理解题意。

大致思路

题目要求的是无论大军怎么移动，都要使所到的地点阵法已开启。

我们就可以直接求最坏情况------大军不走回头路时。

就是从根节点一直到叶子节点。（简单来说就是dfs）

可以证明的，走回头路的方案一定比直接走那条路的方案差。

当搜索到一个节点时，可以定义一个cnt表示到现在位置至少要多少人。

定义一个s表示剩余劳动力。（单位人·小时）

定义一个sd表示当前深度（添加人员时要把他之前的可用劳动力加上）

定义一个len表示当前节点的儿子个数。

当len小于等于s+cnt时，我们可以得到以下式子：

否则，我们又可以得到以下式子：

一旦搜到叶子节点，答案对cnt取max即可。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=300005;
int read()
{   
    int an=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
        an=(an<<1)+(an<<3)+c-'0';
    return an;
}
int n,a[N];
vector <int> G[N];
int cnt,sd=1,s,ans;
void dfs(int t,int q)
{
    int x,tt;
    int bj=0;
    int len=G[t].size()-1;//减去父亲节点
    if(t==1)len++;//根节点没有父亲节点
    if(len==0)
    {
        ans=max(ans,cnt);
        return;
    }
    if(cnt+s<len)
    {
        bj=1;
        x=len-s-cnt+sd-1;//为了回溯方便
        x/=sd;
        tt=s;
        s=x*sd+cnt+s-len;
        cnt+=x;
    }
    else
    {
        tt=cnt-len;
        s+=tt;
    }
    sd++;
    for(int i=0;i<=len;i++)
        if(G[t][i]!=q)
            dfs(G[t][i],t);
    sd--;
    if(bj==1)
    {
        cnt-=x;
        s=tt;
    }
    else
    {
        s-=tt;
    }
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

时间复杂度大致是o(n)的。

还有记得回溯。