首页 > 代码库 > [bzoj4726]Sabota

[bzoj4726]Sabota

做的题太少,什么都要看题解..

题意只给出一个叛徒,则他一定是叶子结点(最坏情况下),那么“带头反叛”的点一定构成了一条链。

令f[u]表示u不带头反叛的最小值,则考虑它的每一支儿子v,(不反叛)f[v],(反叛)size[v]/(size[u]-1),这里取一个min。

因为是最坏情况,所以对所有儿子取max。

现在来考虑答案如何构造(这个我写完想了很久),对于std中ans=max(ans,f[u])的做法(size[u]>k),

先证必要性:显然,每一棵size大于K的子树,我们不能取满,ans至少要达到f[u]。

再证充分性:我们只是对每一棵size大于K的子树进行了询问。也许它们f[u]中的选择是不合法的,却不会影响答案;再者,最开始到达K的子树一定不能带头反叛,那么它就不需要再对上进行转移。所以严格来讲某题解的std还少了一句话【已经标记】,只是不知道为何能过。(也许不写也是正确的吧,牵扯到一堆不等式,反正我证不出来)

技术分享
#include<cstdio>
#include<algorithm>
#define eps 1e-8
#define N 1000010
using namespace std;
int edgenum,n,K;
int vet[N],head[N],size[N],son[N],next[N];
double f[N];
double ans=0;
void add(int u,int v){
    edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
}
void dfs(int u){
    int e=head[u];size[u]=1;son[u]=0;
    while(e>0){
        int v=vet[e];
        dfs(v);
        son[u]+=size[v];size[u]+=size[v];
        e=next[e];
    }
    e=head[u];if(e==0){
        f[u]=1.0;
        if(size[u]>K)ans=max(ans,f[u]);
        return;
    }
    while(e>0){
        int v=vet[e];
        if(size[v]>K){e=next[e];continue;}///////////That‘s it! 
        f[u]=max(f[u],min(f[v],1.0*size[v]/(size[u]-1)));
        e=next[e];
    }
    if(size[u]>K){
        ans=max(ans,f[u]);
    }
}
int main()
{
    scanf("%d%d",&n,&K);
    for(int i=2;i<=n;i++){
        int x;scanf("%d",&x);
        add(x,i);
    }
    dfs(1);
    printf("%.10lf",ans);
}
bzoj4726

 

[bzoj4726]Sabota