洛谷$P4322 [JSOI2016]$最佳团体 二分+$dp$

正解:二分+$dp$

解题报告:

传送门$QwQ$

这题长得好套路嗷,,,就一看就看出来是个$01$分数规划+树形$dp$嘛$QwQ$.

考虑现在二分的值为$mid$,若$midleq as$,则有$frac{sum p_i}{sum s_i}geq mid,sum p_i-midcdot sum s_igeq 0$.

于是就把每个点的点权改为$midcdot s-p$.现在变成要选$K$个节点使得点权之和取$max$.

于是就树形$dp$呗?设$f_{i,j}$表示点$i$的子树中选了$j$个点的$max$,转移的时候强制点$i$必须要选就成.

$over$.

 

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define lf double
#define gc getchar()
#define t(i) edge[i].to
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=2500+10,inf=1e9;
const lf eps=1e-5;
int n,K,sz[N];
lf f[N][N],q[N],tmp[N];
vector<int>V[N];
struct node{int s,p;}nod[N];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il void merg(ri x,ri y)
{
    rp(i,0,K)tmp[i]=-inf;
    rp(i,1,sz[x])rp(j,1,min(K-i,sz[y]))tmp[i+j]=max(f[x][i]+f[y][j],tmp[i+j]);
    rp(i,0,K)f[x][i]=max(f[x][i],tmp[i]);
}
void dfs(ri nw){ri siz=V[nw].size();sz[nw]=1;rp(i,0,siz-1)dfs(V[nw][i]),merg(nw,V[nw][i]),sz[nw]+=sz[V[nw][i]];}
il bool check(lf dat){memset(f,-63,sizeof(f));rp(i,0,n)f[i][1]=nod[i].p-dat*nod[i].s;dfs(0);return f[0][K]>=0;}

int main()
{
    freopen("4322.in","r",stdin);freopen("4322.out","w",stdout);
    K=read()+1;n=read();rp(i,1,n){nod[i]=(node){read(),read()};V[read()].push_back(i);}
    lf l=0,r=10000;while(r-l>=eps){lf mid=(l+r)/2;if(check(mid))l=mid;else r=mid;}printf("%.3lf
",r);
    return 0;
}