首页 > 代码库 > BZOJ 4726: [POI2017]Sabota?

BZOJ 4726: [POI2017]Sabota?

Description

给一棵树,求最小的一个比例使得是叛徒的人数不超过k.

Sol

树形DP.

一开始直接写了个二分...然后T了...复杂度应该挺科学...但是常数大...

然后看见了树形DP的做法...

Code

/**************************************************************    Problem: 4726    User: BeiYu    Language: C++    Result: Accepted    Time:12456 ms    Memory:37616 kb****************************************************************/ #include <cstdio>#include <vector>#include <iostream>using namespace std; #define debug(a) cout<<#a<<"="<<a<<endlconst int N = 500005; int n,k;vector< int > g[N];int sz[N];double f[N];double ans; inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar();    while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; } void DFS(int u,int fa){    sz[u]=1;for(int i=0,lim=g[u].size(),v;i<lim;i++) v=g[u][i],DFS(v,u),sz[u]+=sz[v];}void DP(int u,int fa){    if(sz[u]==1){ f[u]=1.0;return; }    for(int i=0,lim=g[u].size(),v;i<lim;i++) {        v=g[u][i],DP(v,u),f[u]=max(f[u],min(f[v],(double)sz[v]/(sz[u]-1)));    }if(sz[u]>k) ans=max(ans,f[u]);}int main(){    n=in(),k=in();    for(int i=2,u;i<=n;i++) u=in(),g[u].push_back(i);    DFS(1,0);    DP(1,0);    printf("%.8lf\n",ans);    return 0;}

  

BZOJ 4726: [POI2017]Sabota?