bzoj 4753 最佳团体

Written with StackEdit.

Description

\(JSOI\)信息学代表队一共有N名候选人，这些候选人从\(1\)到\(N\)编号。方便起见，\(JYY\)的编号是\(0\)号。每个候选人都由一位编号比他小的候选人\(R_i\)推荐。如果\(R_i=0\)则说明这个候选人是\(JYY\)自己看上的。为了保证团队的和谐，\(JYY\)需要保证，如果招募了候选人\(i\)，那么候选人\(R_i\)"也一定需要在团队中。当然了，\(JYY\)自己总是在团队里的。每一个候选人都有一个战斗值P\(_i\)"，也有一个招募费用\(S_i\)"。\(JYY\)希望招募\(K\)个候选人（\(JYY\)自己不算），组成一个性价比最高的团队。也就是，这\(K\)个被\(JYY\)选择的候选人的总战斗值与总招募总费用的比值最大。

Input

输入一行包含两个正整数\(K\)和\(N\)。

接下来\(N\)行，其中第\(i\)行包含\(3\)个整数\(S_i,P_i,R_i\)表示候选人i的招募费用，战斗值和推荐人编号。

对于\(100\%\)的数据满足\(1≤K≤N≤2500,0<S_i,P_i≤10^4,0≤R_i<i.\)

Output

输出一行一个实数，表示最佳比值。答案保留三位小数。

Sample Input

1 2

1000 1 0

1 1000 1

Sample Output

0.001

Solution

\(0/1\)分数规划与树形背包的结合.
目标是最大化\(\sum a_i/\sum b_i\).
考虑二分答案\(x\),若该答案合法,则\(\sum a_i/\sum b_i\geq x\).
移项,有\(\sum a_i-x\cdot \sum b_i\geq 0\).
令每个物品的权值为\(a_i-x\cdot b_i\),则转化为一般的最大化总权值的树形背包.得出最大总权值后,若其非负,则说明\(x\)合法,否则不合法.

#include<bits/stdc++.h>

#define inf 1e9

using namespace std;

typedef long long LoveLive;

const double eps=1e-5;

inline int read()

{

	int out=0,fh=1;

	char jp=getchar();

	while ((jp>'9'||jp<'0')&&jp!='-')

		jp=getchar();

	if (jp=='-')

		{

			fh=-1;

			jp=getchar();

		}

	while (jp>='0'&&jp<='9')

		{

			out=out*10+jp-'0';

			jp=getchar();

		}

	return out*fh;

}

const int MAXN=2510;

int a[MAXN],b[MAXN],Fa[MAXN];//p,s,r

int cnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];

double w[MAXN],f[MAXN][MAXN];

int sons[MAXN],siz[MAXN];

inline void add(int u,int v)

{

	++cnt;

	to[cnt]=v;

	nx[cnt]=head[u];

	head[u]=cnt;

}

int n,k;

void dfs(int u)

{

	siz[u]=1;

	f[u][0]=0;

	if(sons[u]==0)

		{

			f[u][1]=w[u];

			return;

		}

	for(int i=head[u];i;i=nx[i])

		{

			int v=to[i];

			dfs(v);

			int lim=min(k,siz[u]);

			for(int j=lim;j>=0;--j)

				{

					for(int p=0;p<=siz[v];++p)

						{

							if(j+p>k)

								break;

							f[u][j+p]=max(f[u][j+p],f[u][j]+f[v][p]);

						}

				}

			siz[u]+=siz[v];

		}

	for(int i=k;i>=0;--i)

		{

			if(i>=1)

				f[u][i]=f[u][i-1]+w[u];

			else

				f[u][i]=0;

		}

}

int check(double x)

{

	for(int i=1;i<=n;++i)

		w[i]=1.0*a[i]-1.0*b[i]*x;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			f[i][j]=-inf;

	dfs(1);

	if(f[1][k]>-eps)

		return 1;

	return 0;

}

int main()

{

	k=read(),n=read();

	++n,++k;

	for(int i=2;i<=n;++i)

		{

			b[i]=read();

			a[i]=read();

			Fa[i]=read();

			++Fa[i];

			++sons[Fa[i]];

			add(Fa[i],i);

		}

	double L=0,R=1e4,ans=0;

	while(R-L>eps)

		{

			double mid=(L+R)/2;

			if(check(mid))

				{

					ans=mid;

					L=mid;

				}

			else

				R=mid;

		}

	printf("%.3f\n",ans);

	return 0;

}

巴特西