题目描述
有一棵 $n$ 个节点的完全二叉树,每个节点有 $a_i$ 个苹果,有 $m$ 个用户,每个人会购买一条路径 $(u_i,v_i)$ 上的苹果,保证 $u_i$ 是 $v_i$ 的祖先。第 $i$ 个人最多买 $c_i$ 个苹果,每个苹果支付 $w_i$ 元。问最大付钱数,多测。
数据范围
$n,m \le 10^5;\sum n,\sum m \le 10^6;w_i \le 10^4;c_i,a_i\le 10^9$
题解
暴力的话费用流即可。
考虑费用流的过程,发现我们是 $w_i$ 从大往小占用流量,贪心的想应该是先放在深度深的地方,然后当有新的 $w_i$ 来的时候再为它让路。这个过程用 $set$ 维护即可。由于树高不高,所以每个点只会拆出 $log$ 个点,效率为 $O(nlog^2n)$ 。
代码
#include <bits/stdc++.h> #define LL long long #define _(d) while(d(isdigit(c=getchar()))) using namespace std; const int N=1e5+5; int Rd(){char c;_(!);int x=c^48;_()x=(x<<3)+(x<<1)+(c^48);return x;} int T,n,m,a[N]; LL ans; struct O{int u,v,c,w;}p[N]; bool cmp(O A,O B){return A.w>B.w;} struct Q{ int x,y; friend bool operator < (const Q& A,const Q& B){ if (p[A.x].u==p[B.x].u) return A.x<B.x; return p[A.x].u<p[B.x].u; } }; multiset<Q>s[N]; int ins(int x,int i,int c){ if (x<p[i].u) return 0; int fl=0; if (a[x]){ int v=min(a[x],c); a[x]-=v;c-=v;fl+=v; s[x].insert((Q){i,v}); } if (c) for (Q u;;){ u=*s[x].begin(); if (p[u.x].u<p[i].u){ s[x].erase(s[x].begin()); int v=ins(x>>1,u.x,min(c,u.y)); fl+=v;c-=v;if (v) s[x].insert((Q){i,v}); if (v<u.y){ s[x].insert((Q){u.x,u.y-v});break; } if (!c) break; } else break; } if (c) fl+=ins(x>>1,i,c);return fl; } void work(){ n=Rd(),m=Rd();ans=0; for (int i=1;i<=n;i++) a[i]=Rd(),s[i].clear(); for (int u,v,c,w,i=1;i<=m;i++) u=Rd(),v=Rd(),c=Rd(),w=Rd(), p[i]=(O){u,v,c,w}; sort(p+1,p+m+1,cmp); for (int i=1;i<=m;i++) ans+=1ll*ins(p[i].v,i,p[i].c)*p[i].w; printf("%lld\n",ans); } int main(){ for (T=Rd();T--;work()); return 0; }