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