M_sea

洛谷4322 [JSOI2016]最佳团体
LuoguBZOJ分析还是比较好像的吧qwq要求最大的比值,一看就是分数规划。二分答案$mid$,然后推一发:$\...
扫描右侧二维码阅读全文
11
2019/01

洛谷4322 [JSOI2016]最佳团体

Luogu

BZOJ

分析

还是比较好像的吧qwq

要求最大的比值,一看就是分数规划。

二分答案$mid$,然后推一发:

$\large\frac{\sum p_i}{\sum s_i}>mid\\\sum p_i>mid\times \sum s_i\\\sum p_i-mid\times\sum s_i>0\\\sum p_i-\sum mid\times s_i>0$

这就比较明显了。因为原题是一棵树,考虑树上背包,将$p_i-mid\times s_i$作为价值就行了。

注意$k$是不包括题目中的主人公自己的,最好读进来就加$1$。

一些吐槽:在Luogu上把下界设成1.8,上界设成2.3依然能AC。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define min(a,b) (((a)<(b))?(a):(b))
#define re register
using namespace std;

inline void chkmax(double& x,double y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=2500+10;

struct Edge { int v,nxt; };
Edge e[MAXN];
int head[MAXN];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int k,n;
int s[MAXN],p[MAXN];
double val[MAXN];
int sz[MAXN];
double f[MAXN][MAXN],g[MAXN];

inline void dfs(int u) {
    f[u][1]=val[u],sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; dfs(v);
        for (re int j=0;j<=k;++j) g[j]=-2e14;
        for (re int j=1;j<=sz[u];++j)
            for (re int l=1;l<=min(sz[v],k-j);++l)
                chkmax(g[j+l],f[u][j]+f[v][l]);
        for (re int j=0;j<=k;++j) chkmax(f[u][j],g[j]);
        sz[u]+=sz[v];
    }
}

inline int check(double mid) { //如果可行返回true
    for (re int i=0;i<=n;++i)
        for (re int j=0;j<=k;++j)
            f[i][j]=-2e14;
    memset(sz,0,sizeof(sz));
    for (re int i=1;i<=n;++i) val[i]=p[i]-mid*s[i];
    dfs(0);
    return f[0][k]>0;
}

int main() {
    k=read()+1,n=read(); //k+1:把自己选进去
    for (re int i=1;i<=n;++i)
        s[i]=read(),p[i]=read(),addEdge(read(),i);
    double L=0,R=1e4; //R再大一点也行?
    while (R-L>1e-4) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
    }
    printf("%.3f\n",L);
    return 0;
}
最后修改:2019 年 01 月 23 日 01 : 03 PM

发表评论