自动搬运

查看原文

来自洛谷，原作者为

	mulberror 把回忆远远的放逐，流星划过寂夜里的深处，碎梦沉沦在眼前起舞。

搬运于2025-08-24 21:27:26，当前版本为作者最后更新于2018-10-20 23:15:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

既然没有人来题解那么我就来一篇吧！

这个题目的算法叫做01分数规划。

我的博客里面有非常详细的讲解，安利一下

---

好了，我们废话不说，来讲解一下。

01分数规划的题目有一个比较明显的特点，就是一般是要算出

$$\frac{\sum wi}{\sum vi}$$

而这个公式中的wi表示每个物品的价值，vi表示代价。

01分数规划问题主要包含以下几个问题：

• 一般的01分数规划
• 最优比率生成树
• 最优比率环

---

关于01分数规划的关键

F(L)=sigma(a[i]x[i])-Lsigma(b[i]*x[i])

F(L)=sigma(a[i]x[i]-Lb[i]*a[i])

F(L)=sigma((a[i]-L*b[i])*x[i])

我们把a[i]-L*b[i]定义为d[i]，这样我们的算式就变成了以下算式。

F(L)=sigma(d[i]*x[i])

这样我们就把这个繁琐的算式变成了一个非常优美的算式。 而01分数规划就是要枚举L在求最大值或最小值的F(L)。 在实现程序的过程中，我们使用一个非常熟悉的老朋友，要求最大或最小，所以？？我们就要用二分

---

关于为什么01分数规划不能用贪心？

（个人看法） 如果硬要贪心，那么就只有可能是算出每一个物品的性价比，在排序求出最大或者最小的性价比，在累加算出答案。

一、01分数规划算法

先设置价值数组a[i]和代价数组b[i]，我们的答案为R。

$$R= \frac{\sum_{i=1}^{n}{a[i]*x[i]}}{\sum_{i=1}^{n}{b[i]*x[i]}} $$

简单来说 $$ R=\frac{\sum{valuei}}{\sum{weighti}} $$ 我们可以发现，R的大小与上下的总值有关。

二、贪心算法

我们反观一下贪心算法，先算出每个物品的性价比

$$xi=\frac {valuei}{weighti}$$

那么贪心得到的答案就是

$$R=\sum{xi}$$

比较

我们可以很容易发现，01分数规划和贪心的得到的答案有明显的区别，一个是总价值/总代价，而贪心中只是单价值/单代价的累加，而不只是比值的大小，而取决于分母和分子的大小，所以这两个东西不相等

---

那么我们回到这一道题目，看到比值我们要想到用01分数规划，然后我们二分枚举一下这个以上的L，在进行检查就可以了。

判断就是做一下树背包，求树上一个n - m的连通块，使块中的点的权值之和最大。

令$dp[u][j]$表示以u为根的子树中，有一个点数为 j 的联通块时的最大值。这个联通块一定是包含u的。

动态转移方程:$$ f[u][j]=Max(f[u][j],f[u][j-k]+f[v][k]); $$

u是当前节点，v是儿子，j和k是要自己枚举的

#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
const int Maxn=105;
const int Inf=1<<30;
const double eps=1e-4;
struct Edge{
	int to,next;
}edge[Maxn<<1];
double d[Maxn],f[Maxn][Maxn];
int v[Maxn],c[Maxn],sz[Maxn],head[Maxn];
int n,m,Nedge;
inline int Min(int n,int m) {return n<m?n:m;}
inline int Max(int n,int m) {return n>m?n:m;}
inline int read() {
	int w=0,x=0;char ch=0;
	while (!isdigit(ch)) {w|=ch=='-';ch=getchar();}
	while (isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
inline void Add_Edge(int u,int v) {//邻接表建图
	edge[Nedge]=(Edge){v,head[u]};
	head[u]=Nedge++;
}
inline void dfs(int u,int fa) {//树背包
	sz[u]=1;//将当前节点的子树节点设置为1
	f[u][0]=0;//初始化
	for (int i=head[u];i!=-1;i=edge[i].next) {//专属for
		int v=edge[i].to;
		if (v==fa) continue;//如果v=fa那么就跳出
		dfs(v,u);//递归子树
		sz[u]+=sz[v];//将子树的个数加到自己身上
		for (int j=Min(m,sz[u]);j>=0;j--) {
			for (int k=0;k<=Min(j,sz[v]);k++) 
				f[u][j]=Max(f[u][j],f[u][j-k]+f[v][k]);//背包
		}
	}
	for (int i=min(m,sz[u]);i>0;i--) f[u][i]=f[u][i-1]+d[u];
}
inline bool judge(double x) {
	for (int i=1;i<=n;i++) 
		for (int j=0;j<=m;j++) f[i][j]=-Inf;
	for (int i=1;i<=n;i++) d[i]=(v[i]*1.0)-x*(1.0*c[i]);//01分数规划的基本操作
	dfs(1,0);
	for (int i=1;i<=n;i++) 
		if (f[i][m]>-eps) return 1;
	return 0;
}
int main() {
	ms(head,-1);
	n=read(),m=read();
	for (int i=1;i<=n;i++) v[i]=read();
	for (int i=1;i<=n;i++) c[i]=read();
	m=n-m;
	for (int i=1;i<n;i++) {
		int a=read(),b=read();
		Add_Edge(a,b);
		Add_Edge(b,a);
	}
	double l=0,r=1000000;
	while (r-l>eps) {//在容许范围内那么就输出
		double Mid=(l+r)/2.00;
		if (judge(Mid)) l=Mid;
		else r=Mid;
	}
	printf("%.1lf\n",l);
	return 0;
}