题解 P1642 【规划】

· · 题解

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

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

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

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

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

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

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

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]-Lb[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;
}