【DSY-2117】摩尔庄园

· · 个人记录

2117: 摩尔庄园

从前，有一个地方叫作摩尔庄园。摩尔庄园里有 n 座房子，编号为1到n。房子与房子之间有隧道连接。由于建造者们很懒，它们只建了 n−1 条隧道，每条隧道长度为1。对于编号 i(i>1) 的房子，有一条连向编号为 \left\lfloor\frac{i}{2}\right\rfloor 的房子的隧道。隧道是双向的。对于每间房子，我们知道这间房子有 ci 份食物可供最多 ci 只拉姆们食用。

在这庞大的 n 座房子中，住着 m 只拉姆，编号从1到m。对于第 i 只拉姆，它一开始住在编号为 pi 的房子里。所有拉姆一开始都是处于睡眠状态。第二天早上，编号小于等于 k 的拉姆起床了，而其它 m−k 只拉姆仍保持睡眠状态。这 k 只拉姆会选择有食物的房子然后爬过去。它们想知道，在保证这 k 只拉姆都有食物吃的前提下，它们爬行距离的总和的最小值是多少。

记 k 只拉姆爬行距离的总和的最小值为 f(k) ，你需要输出 f(1),f(2),f(3),...,f(m) 。

思路

树形 dp + 网络流

用树形 dp 模拟网络流。

1

很明显，题目给出的是一棵完全二叉树。

预处理，维护在当前每个房子的子树（含自己）中，距离它最近的、有食物的房子的编号与距离。

然后每次输入一个 p_i，即第 i 只拉姆的位置，求出当前最优解（保留之前答案）。

也就是说，在计算完只有一只拉姆时的答案之后，在此状态下（第一只拉姆吃掉了最近的食物）计算第二只拉姆吃到食物的距离。

2

按照这样的做法，显然，无法保证答案最优。

所以要模拟网络流。

图

如图所示， 按照 1 中述的做法，无法由图中第一情况得到图中第二情况。

因为，在第一只拉姆吃掉 4 号房子的食物后，第二只拉姆会走到 5，路程为 2，去吃食物。

因此，设 flow_i 表示经过 i 点和它父亲之间的树边的次数。

若由一个流自点 i 的儿子或它本身，通向点 i 的父亲，即自该点经过了该点和它父亲之间的树边，则 flow_i \gets1；反之减 1。

再设每条树边的初始费用为 1，

这样的目的是抵消。

以上述自儿子通向父亲时 flow_i<0 的情况为例，因为 flow_i<0，所以意味着有更多的流自该树边的父亲走向了儿子，那么费用为 -1，就可以和之前自父亲通向儿子、费用为 1 的路抵消。

3

每次计算距离时，从该拉姆的起始点向上走，每次看当前走到的节点，从它走向它子树最近的、有食物的房子的距离是否能刷新最小值，最后取这个最小值即可。

计算完之后，再更新一下每个节点的流量，维护一下每个节点最近的食物点。

代码

一定要记得先给 dis 赋值一个最大值。

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

#define maxn 200005
#define rep(i, a, b) for(int i = a; i <= b; ++i)

int n, m, c[maxn];
int ans, dis[maxn], pos[maxn], flw[maxn];
int s, t, tt, nw, cst;

inline int Flow(int x, int fx)
{
    if(fx == 1)//up
        return flw[x] < 0 ? -1 : 1;
    else//down
        return flw[x] > 0 ? -1 : 1;
}

inline void updt(int x)
{
    int l = x << 1, r = x << 1 | 1;
    dis[x] = 2e9, pos[x] = 0;
    if(c[x])
        dis[x] = 0, pos[x] = x;
    if(dis[x] > dis[l] + Flow(l, 0))
        dis[x] = dis[l] + Flow(l, 0), pos[x] = pos[l];
    if(dis[x] > dis[r] + Flow(r, 0))
        dis[x] = dis[r] + Flow(r, 0), pos[x] = pos[r];
}

int main()
{
    memset(dis, 127 / 3, sizeof dis);
    scanf("%d %d", &n, &m);
    rep(i, 1, n) scanf("%d", &c[i]);
    for(int i = n; i >= 1; --i) updt(i);
    while(m--)
    {
        cst = 2e9, nw = t = 0;
        scanf("%d", &s);
        for(int i = s; i; i >>= 1)
        {
            if(cst > dis[i] + nw)
                cst = dis[i] + nw, t = i;
            nw += Flow(i, 1);
        }
        tt = pos[t], ans += cst;
        for(int i = s; i > t; i >>= 1) flw[i] += 1;
        for(int i = tt; i > t; i >>= 1) flw[i] -= 1;
        c[tt] -= 1;
        for(int i = tt; i > t; i >>= 1) updt(i);
        for(int i = s; i; i >>= 1) updt(i);
        printf("%d ", ans);
    }
    return 0; 
}

——End——