BZOJ.4753.[JSOI2016]最佳团体(01分数规划 树形背包DP)

时间:2021-10-20 23:01:21

题目链接

\(Description\)

每个点有费用si与价值pi,要求选一些带根的连通块,总大小为k,使得 \(\frac{∑pi}{∑si}\) 最大

\(Solution\)

01分数规划,然后dp,设f[i][j]表示i子树选j个的最大权值和,直接暴力背包转移即可

在枚举子节点选的数量时,假设x有1.2.3.4四个子节点,复杂度为 \(1*sz[1]+sz[1]*sz[2]+(sz[1]+sz[2])*sz[3]+(sz[1]+sz[2]+sz[3])*sz[4]\)

相当于每对点在LCA处有贡献,共会有n2对点,所以这部分复杂度为O(n2)

总O(n^2*log ans)

注: 初始值不要是0,因为会有较大负数。比如说 必须规定f[0][1]为-INF

eps为什么需要1e-5。。<1e-4结束不行吗(也许是因为这并不是精确答案?卡时大法好)

还可以在DFS序上DP?https://blog.csdn.net/CHN_JZ/article/details/78724391

//50024 kb    3512 ms 好慢啊。。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=2505;
const double eps=1e-5,INF=1e10; int n,m,Enum,H[N],nxt[N],to[N],sz[N];
double cost[N],p[N],val[N],f[N][N]; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
void DFS(int x)
{
int mn=(x>0); sz[x]=mn;
for(int i=2; i<=m; ++i) f[x][i]=-INF;
f[x][1]=val[x];
for(int v,i=H[x]; i; i=nxt[i])
{
DFS(v=to[i]);
for(int j=sz[x]; j>=mn; --j)//倒序 //更新上限就是当前已有sz与子节点sz之和
for(int k=1; k<=sz[v]; ++k)
f[x][j+k]=std::max(f[x][j+k],f[x][j]+f[v][k]);
sz[x]+=sz[v];
}
}
double Solve(double x)
{
for(int i=1; i<=n; ++i) val[i]=p[i]-x*cost[i];
// memset(f,0xc2,sizeof f), f[0][0]=0;//too slow
DFS(0);
return f[0][m]>=0;
} int main()
{
m=read(), n=read();
for(int i=1; i<=n; ++i)
cost[i]=read(),p[i]=read(),AddEdge(read(),i);
double l=0.0,r=1e4,mid; val[0]=-INF;//f[0][1]
while(r-l>eps)
{
if(Solve(mid=(l+r)/2.0)) l=mid;
else r=mid;
}
printf("%.3lf",mid); return 0;
}