题解 P3006 【[USACO11JAN]瓶颈Bottleneck】

· · 题解

打广告->这里

感觉这题的思路还是挺不错的。然而为啥全网就一个题解而且只有代码……然后我只好看着代码理解了好久……

题意就是有一棵树，每一个节点向他父亲节点连边，且有一个容量表示每一秒可以经过的牛的数量，每一个点有一堆牛，在满足容量限制的情况下可以不断往祖先跳直到跳到1节点。然后问你在保证总时间最短的情况下第t秒1节点有多少头牛

首先，不难发现一个贪心，就是如果向父亲的边能够流满的时候，流满一定比不流满优

那么我们令每一条边都强制流满，然后对每个点记录一个值pass[i]，值为它能向父亲流的最大的流量减去它的儿子们向它流的最大流量，不难发现它代表如果每条边都流满之后每秒能有多少头牛离开这个点向祖先去。

那么我们设每一个节点开始时牛的个数为cow[i]，那么，cow[i]/pass[i]就代表这一个节点的所有牛都走光所需要的时间

那么令t=cow[i]/pass[i]，当时间小于等于t的时候，我们需要考虑这一个点还剩下多少头牛。当时间大于t的时候，我们已经不需要再考虑这个点还剩下多少头牛了，因为可以在满流之后让它所有的牛都到它的父亲那里去。那么，我们可以把它和它的父亲看做同一个点，牛的数量为两个点之和，pass[fa[i]]也是两个点之和（它和父亲之间的那条边的流量因为父亲减一次它加一次已经抵消了），然后再对这个点记录一个新的t就好了。这个可以用一个并查集维护

那么，我们对询问按时间排序。当询问的时间大于当前t的时候，我们把所有t小于等于询问的时间的点全都和它的父亲给并起来。当询问的时间小于等于当前t时，答案就是cow[1]+pass[1]*询问的时间（cow[1]代表所有已经被缩到这一个点的总的牛的数量，然后1点的pass肯定是负数，所以减去就相当于加上这个点的儿子的点全都满流向它流，在询问的这段时间里能流多少）

然后总不可能维护时间轴……所以开个优先队列把所有点的t给扔进去就好了，反正就这些点的t有用

讲的应该还蛮清楚的吧……

// luogu-judger-enable-o2
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read(){
    #define num ch-'0'
    char ch;bool flag=0;ll res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(ll x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=100005;
struct query{ll t,res;int id;}ask[N];
inline bool cmp1(query x,query y){return x.t<y.t;}
inline bool cmp2(query x,query y){return x.id<y.id;}
struct node{
    ll t;int x;node(){}
    node(ll t,int x):t(t),x(x){}
    inline bool operator <(const node &b)const
    {return t>b.t;}
};
priority_queue<node> q;
int fa[N],f[N],lim[N];ll cow[N],pass[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int n,m;
int main(){
//  freopen("testdata.in","r",stdin);
    n=read(),m=read();
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=2;i<=n;++i)
    f[i]=read(),cow[i]=read(),lim[i]=read(),pass[f[i]]-=lim[i],pass[i]+=lim[i];
    for(int i=1;i<=m;++i)
    ask[i].t=read(),ask[i].id=i;
    sort(ask+1,ask+1+m,cmp1);
    for(int i=2;i<=n;++i)
    if(pass[i]>0)
    q.push(node(cow[i]/pass[i],i));
    int l=1,x,tp;
    while(!q.empty()&&l<=m){
        while(l<=m&&ask[l].t<=q.top().t)
        ask[l].res=cow[1]-pass[1]*ask[l].t,++l;
        if(fa[q.top().x]!=q.top().x){q.pop();continue;}
        x=q.top().x,tp=find(f[x]),cow[tp]+=cow[x];
        pass[tp]+=pass[x],fa[x]=tp;
        if(pass[tp]>0) q.push(node(cow[tp]/pass[tp],tp));
        q.pop();
    }
    sort(ask+1,ask+1+m,cmp2);
    for(int i=1;i<=m;++i) print(ask[i].res);
    Ot();
    return 0;
}