ecnuoj 5039 摇钱树

5039. 摇钱树

题目链接:5039. 摇钱树

感觉在赛中的时候,完全没有考虑分数规划这种做法。同时也没有想到怎么拆这两个交和并的式子。有点难受……

当出现分数使其尽量大或者小,并且如果修改其中直接相关的某个值会导致分子分母同时变化的时候,还是要多想想分数规划的做法。

下面引用一下题解

另外这两个交和并的式子,令 \(a = S \and T, b = T - a\),所以原来的式子变成了

\[\frac{|S \and T|}{|S \or T|} = \frac{a}{b + |S|}
\]

所以,用分数规划的做法,二分一个答案 \(ans\),则有

\[\frac{a}{b + |S|} \ge ans \implies a - b \cdot ans \ge |S|\cdot ans
\]

接下来用树上 dp 求一个最大的 \(a - b \cdot ans\) 即可。

\(f_{i,j}\) 表示此时 \(i\) 号点上选了 \(j\) 个子树加和起来最大的 \(a-b\cdot ans\) 值,\(x_{i,j}\) 表示这个式子中的 \(a\)\(y_{i,j}\) 表示这个式子中的 \(b\)

那么接下来就是一个普通的树上背包的转移了,不过区别在于转移完整个 \(f_u\) 后,需要再用取整个以 \(u\) 为根构成的一颗子树去更新一下 \(f_{u,1}\)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;

#define IL inline
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl

template<typename Tp> IL void read(Tp &x) {
    x=0; int f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    x *= f;
}
int buf[42];
template<typename Tp> IL void write(Tp x) {
    int p = 0;
    if(x < 0) { putchar('-'); x=-x;}
    if(x == 0) { putchar('0'); return;}
    while(x) {
        buf[++p] = x % 10;
        x /= 10;
    }
    for(int i=p;i;i--) putchar('0' + buf[i]);
}

const int N = 100000 + 5;
const int M = 50 + 5;
int n, m;
int a[N], suma[N], sz[N], x[N][M], y[N][M];
db f[N][M];
vector<int> G[N];

struct fs {
    int fz, fm;
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}
    fs(int fz=0, int fm=1) {
        if(fz == 0) this -> fm = 1;
        else {
            int g = gcd(fz, fm);
            this -> fz = fz / g;
            this -> fm = fm / g;
        }
    }
};

int dfs2(int u, int fa, const db& ef_x) {
    int u_leaf = 0;
    if(u != 1 && G[u].size() == 1) {
        if(a[u] == 1) {
            f[u][1] = 1.0;
            x[u][1] = 1; y[u][1] = 0;
        }
        return ++u_leaf;
    }
    for(int i=0;i<=m;i++) f[u][i] = x[u][i] = y[u][i] = 0;
    for(int v : G[u]) {
        if(v == fa) continue;
        int v_leaf = dfs2(v, u, ef_x);
        for(int i=min(u_leaf,m);i>=0;i--) {
            for(int j=1;j<=v_leaf && i+j <= m; j++) {
                if(f[u][i] + f[v][j] > f[u][i+j]) {
                    f[u][i+j] = f[u][i] + f[v][j];
                    x[u][i+j] = x[u][i] + x[v][j];
                    y[u][i+j] = y[u][i] + y[v][j];
                }
            }
        }
        u_leaf += v_leaf;
    }
    if(suma[u] - (sz[u] - suma[u]) * ef_x >= f[u][1]) {
        f[u][1] = suma[u] - (sz[u] - suma[u]) * ef_x;
        x[u][1] = suma[u];
        y[u][1] = sz[u] - suma[u];
    }
    return u_leaf;
}

array<int, 3> check(const db& x) {
    dfs2(1, 0, x);
    int ansu = 1, ansi = 1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        if(f[i][j] > f[ansu][ansi]) {
            ansu = i; ansi = j;
        }
    }
    return {f[ansu][ansi] >= suma[1] * x, ansu, ansi};
}

void dfs1(int u, int fa) {
    suma[u] += a[u];
    sz[u] = 1;
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        suma[u] += suma[v];
        sz[u] += sz[v];
    }
}

void solve() {
    read(n); read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++) {
        int u, v; read(u); read(v);
        G[u].pb(v); G[v].pb(u);
    }
    dfs1(1, 0);
    db L = 0.0, R = 1.0;
    fs ans;
    while(R - L >= 1e-10) {
        db M = (L + R) / 2.0;
        auto arr = check(M);
        if(arr[0]) {L = M; ans = fs(x[arr[1]][arr[2]], y[arr[1]][arr[2]] + suma[1]);}
        else R = M;
    }
    write(ans.fz); putchar(32); write(ans.fm); putchar(10);
}

int main() {
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
#endif
    int T = 1;
    // read(T);
    while(T--) solve();
    return 0;
}

原文链接:https://www.cnblogs.com/bringlu/p/17284738.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:ecnuoj 5039 摇钱树 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • python 实现插入排序算法

    以下是关于“Python实现插入排序算法”的完整攻略: 简介 插入排序算法是一种简单的排序算法,它的基本思想是将一个元素插入到已排序的序列中,从而得到一个新的有序序列。在本教程中,我们将介绍如何使用Python实现插入排序算法,并提供两个示例。 方法步骤 插入排序算法的Python实现方法步骤如下: 遍历待排序序列,从第二个元素开始。 将当前元素插入到已排序…

    python 2023年5月14日
    00
  • 详解快速排序算法原理与使用方法

    快速排序算法是一种基于比较的排序算法,其使用递归的方法对待排序序列进行排序。快速排序的特点是可以通过递归的方式,在每次排序中选择一个元素作为枢轴(pivot),将待排序序列分成两个部分,其中一个部分所有元素都比枢轴小,另一个部分所有元素都比枢轴大,然后对这两个部分分别递归进行快速排序,直到所有元素都排序完成。 下面是快速排序算法的完整攻略: 快速排序的基本思…

    算法 2023年3月27日
    00
  • PHP常用算法和数据结构示例(必看篇)

    PHP常用算法和数据结构示例(必看篇)攻略 在这篇文章中,我们将会学习一些PHP常用的算法和数据结构,并通过一些示例来说明它们的应用场景和使用方法。 1. 哈希表 哈希表是一种常用的数据结构,它根据关键码值(Key Value)而直接进行访问的数据结构。哈希表通常用于实现关联数组。PHP中提供了内置的哈希表数据结构Map和Array。 1.1 使用Map实现…

    数据结构 2023年5月17日
    00
  • python数据结构之二叉树的统计与转换实例

    下面是针对“python数据结构之二叉树的统计与转换实例”的详细讲解攻略: 什么是二叉树 二叉树指的是一种树状结构,具有如下特点: 每个节点最多有两个子节点,分别为左子节点和右子节点 左子节点的值比父节点小,右子节点的值比父节点大 二叉树可以是空树,也可以是非空树。 二叉树的遍历 在对二叉树进行操作时,需要对其节点进行遍历。二叉树的遍历方式一般有以下三种: …

    数据结构 2023年5月17日
    00
  • C语言数据结构顺序表中的增删改(头插头删)教程示例详解

    C语言数据结构顺序表中的增删改(头插头删)教程示例详解 什么是顺序表? 顺序表是一种用数组实现的线性表,所有元素存储在一块连续的存储区中。顺序表的操作包括插入、删除、查找等。 常用的顺序表操作 增加元素 删除元素 修改元素 查找元素 以下以头插和头删为例,讲解如何在C语言数据结构顺序表中实现这些操作。 头插操作 头插的实现首先需要考虑插入位置的下标,由于是头…

    数据结构 2023年5月17日
    00
  • 带你了解Java数据结构和算法之前缀,中缀和后缀表达式

    带你了解Java数据结构和算法之前缀、中缀和后缀表达式 1. 前缀表达式(Prefix Expression) 前缀表达式是指运算符位于操作数之前的表达式,也被称为波兰式。前缀表达式的优点在于,每个运算符的优先级都可以通过括号来明确,不需要考虑运算符的优先级。同时,整个表达式的意义也可以很清晰地传达。 举个例子,下面是一个前缀表达式: + * 4 5 6 /…

    数据结构 2023年5月17日
    00
  • python二分法查找实例代码

    以下是关于“Python二分法查找实例代码”的完整攻略: 简介 二分法查找是一种常用的查找算法,它通过将有序数组分成两部分,每次查找可以将查找范围缩小一半,从而快速定位目标元素。在本教程中,我们将介绍如何使用Python实现二分法查找,并提供两个示例说明。 实现二分法查找 以下是使用Python实现二分法查找的代码: def binary_search(ar…

    python 2023年5月14日
    00
  • C语言植物大战数据结构希尔排序算法

    C语言植物大战数据结构希尔排序算法 什么是希尔排序 希尔排序是一种基于插入排序的排序算法,也叫做“缩小增量排序”。和插入排序不同的是,希尔排序的插入排序是对一定间隔的元素进行插入排序,而不是对数组中相邻的元素进行排序。 希尔排序的流程和方法 希尔排序的主要流程是根据元素间的间隔d,分组进行插入排序,依次减小d值。最后当d=1的时候,再按照插入排序的方法对整个…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部