A simple Blog for wyx I've been down the bottle hoping.
4753: [Jsoi2016]最佳团体
发表于: | 分类: Oi | 评论:0 | 阅读:200

题目大意
给定一棵树,选择一个节点就必须要选择他的父亲节点,每个点选择会付出一定的代价$P_i$,但是也会获得一个权制$V_i$,现在要选出一个点集,大小为指定的数字$K$,使得整个集合中的点的性价比最高,即$\frac{\sum V_i}{\sum C_i}最大$

显然是01分数规划类问题

我们二分一个答案$ans$,显然对于任意一组解都会有$\sum V_i \le ans\times S_i$

那么也就有$\sum V_i - \sum ans\times S_i \le 0$

然后我们令$T_i = V_i-S_i\times ans$

那么现在就需要验证是否存在点集的$\sum T_i > 0$

设计一个$dp$即可,$f(i,j)$表示在$i$节点下面选了$j$个的$T$的和的最大值,最后判断$f(0,k) ? 0$转移就直接枚举一个子树内选择的点数。注意强制选择$root$就行了

注意到复杂度是$n^2$的,具体的证明大概就是只有$Lca$会消耗复杂度

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2500+5;
const int M = N << 1;
typedef double f2;
typedef long double f4;
const f2 eps = 1e-9;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

f2 F[N][N], a[N];
int K, n, head[N], fa[N], S[N], P[N], size[N];

struct graph {
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y) {
    static int cnt = 0; edge[++cnt] = graph(head[x],y); head[x] = cnt;
}

inline void DFS(int x) {
    size[x] = 1;
    int last = 0;
    register int i, j, k;
    if(x) F[x][1] = a[x], last = 1;
    else F[x][0] = 0;
    for(i=head[x];i;i=edge[i].next) DFS(edge[i].to), size[x] += size[edge[i].to];
    for(i=head[x];i;i=edge[i].next) {
        last += size[edge[i].to];
        for(j=last;j>=0;--j) 
            for(k=0;k<=size[edge[i].to]&&k<=j;++k) 
                F[x][j] = max(F[x][j],F[x][j-k] + F[edge[i].to][k]);
    }
}

inline bool check(f2 mid) {
    memset(F,0xc2,sizeof F);
    for(int i=1;i<=n;++i) a[i] = (f2)P[i] - (f2)S[i]*mid;
    DFS(0);
    return F[0][K] > -eps;
}

int main() {
    K = read(), n = read();
    for(int i=1;i<=n;++i) {
        S[i] = read(), P[i] = read();
        fa[i] = read(); add(fa[i],i);
    }
    f2 L = 0, R = 1e4;
    while(R-L>1e-5) {
        f2 mid = (L+R)/2.0;
        if(check(mid)) L = mid;
        else R = mid;
    }
    printf("%.3lf\n",(L+R)/2);
} 

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP