首页 > 代码库 > 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?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。