题解：P3006 [USACO11JAN] Bottleneck G

· · 题解

比较容易使人思维弄混的一个题。

贪心策略肯定对于任意一个点，只要能往上跑就往上跑，也就是尽量让每一条边都满流。这样直接模拟的话是 O(n^2qt) 或者 O(nqt)。

但复杂度肯定不可能带 t，考虑怎么先把 t 去掉。可以设计一个简单的树形 dp：设 f_{u} 表示 t 秒内经过点 u 流向父亲的最大数量。那么显然有 f_{u}=\min(t \times m_u,(\sum\limits_{v \in son_u} f_v)+c_u)。这样可以做到 O(nq)。

由于这个树形 dp 依赖于 t 的具体值，因此这个做法无法优化。但得到的一个启示是可以往流入流出的方向想。对于一个点 u，如果 m_u > \sum\limits m_v，那么总有一个时刻 t 使得原来在 u 处的牛都流出了，t+1 之后的时刻一定是 v 流向 u 再流向 fa_u，因为点 u 入不敷出，根据一开始的贪心策略肯定会再往上流，相当于这个 u 没有用了。那么我们设 g_{u} 表示这个出入关系，则 g_u=m_u-\sum\limits m_v。那么若 g_u 为正，则当 t > \dfrac{c_u}{g_u} 时 u 就相当于一个中转点要将儿子的流量流向父亲。

然后我们考虑一个这样的树：

很明显在二号点出现“入不敷出”的情况之前，1 号点最终的数量只和 m_2 有关，因为一直是满流。但实际情况可能是来自 345 的流向了 1。但这并不重要，因为我们只关心流了多少而不是来自哪里。当 2 号点不够了之后，实际就是全部的流入都来自 345，相对应的单位时间的流入大小也有改变。那么怎么维护这个信息呢？可以直接把 345 直接连向 1 号点，然后把他们的流量信息合并到 1 号点，这一过程可以并查集维护。

更一般地，若 t > \dfrac{c_u}{g_u}，我们把点 u 并到父亲所在集合的根那里去，然后令 c_{fa_u} \leftarrow c_{fa_u}+c_u,g_{fa_u} \leftarrow g_{fa_u}+g_u。等价于所有儿子直接流向 u 的父亲，且之前流到 u 的都流走了。然后我们需要重新计算新合并的点再次“入不敷出”的时间 t'。需要注意的是，这里的 fa_u 并非是 u 的父亲节点，而是并查集 find 函数找 u 父亲所在的根节点。

通过干这样一件事情，我们保证了当前所有节点都会进行下一次流出（除非已经全部流到 1 号点）。然后小根堆维护一下时间，将询问离线后排序，把经过的时间点依次合并。这样就实时地维护了每个时间点流向 1 号点的流量。因此答案为 c_1-g_1 \times t，其中 t 是当前询问的时间，g_1 是负的所以要减。

复杂度是 O((n+q) \log n)，感觉这个题理解起来还是挺抽象的。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
int n,i,j,ans,k,Q,t,s,m[N],c[N],p[N],g[N],res[N];
std::priority_queue<pii>q;
struct ren{
    int t,w;
    bool operator < (const ren &A) const{
        return t < A.t; 
    }
}d[N];
struct DSU{
    int f[N];
    void init(){
        for(int i=1;i<=n;i++) f[i]=i; 
        return;
    }
    int find(int x){
        if(x==f[x]) return x;
        return f[x]=find(f[x]);
    }
}dsu;
signed main(){
    scanf("%lld%lld",&n,&Q);
    for(i=2;i<=n;i++){
        scanf("%lld%lld%lld",&p[i],&c[i],&m[i]);
        g[p[i]]-=m[i],g[i]+=m[i],s+=c[i];
    }
    for(i=1;i<=n;i++){
        if(g[i]>0) q.push({-c[i]/g[i],i});
    }
    for(i=1;i<=Q;i++) scanf("%lld",&d[i].t),d[i].w=i;
    sort(d+1,d+1+Q);
    dsu.init();
    for(i=1;i<=Q;i++){
        while(!q.empty() && -q.top().fi<d[i].t){//只能< 
            int x=q.top().se;
            q.pop();        
            if(dsu.f[x]!=x) continue;
            int k=dsu.find(p[x]);
            g[k]+=g[x],c[k]+=c[x],dsu.f[x]=k;
            if(g[k]>0) q.push({-c[k]/g[k],k});
        }
        res[d[i].w]=min(s,c[1]-g[1]*d[i].t);
    }
    for(i=1;i<=Q;i++) printf("%lld\n",res[i]);
    return 0;
}