锐客网

  1. 首页 > it技术 > >

【堆模拟费用流增广】UOJ455 [UER #8] 雪灾与外卖

【题目】
原题地址
一条直线上有 n n n个送餐员和 m m m个餐厅。每个送餐员都要去餐厅取菜，花费为距离+菜的价值。每个餐厅有提供菜数量限制，求最小花费。 n , m ≤ 1 0 5 n,m\leq 10^5 n,m≤105，其他数字 ≤ 1 0 9 \leq 10^9 ≤109
【解题思路】
题解看这
设送餐员为 a a a，餐厅为 b b b，坐标为 x x x。
首先我们可以观察到一个十分 naive \text{naive} naive的性质： ? 1 ≤ a i < a j ≤ n , 1 ≤ b k < b l ≤ m , ∣ x a i ? x b k ∣ + ∣ x a j ? x b l ∣ ≤ ∣ x a j ? x b k ∣ + ∣ x a i ? x b l ∣ \forall 1\leq a_i< a_j\leq n,1\leq b_k< b_l\leq m,|x_{a_i}-x_{b_k}|+|x_{a_j}-x_{b_l}|\leq |x_{a_j}-x_{b_k}|+|x_{a_i}-x_{b_l}| ?1≤ai? 于是我们按顺序 DP \text{DP} DP，状态为前 i i i个送餐员匹配到前 j j j个餐厅的最小花费，转移时枚举第 j j j个餐厅匹配多少个送餐员，用单调队列优化可以做到 O ( n m ) O(nm) O(nm)
考虑一个更显然的问题，这个就是一个二分图匹配问题，我们建图跑费用流就可以了。
然而这样做并不优秀，于是我们考虑套路，用堆或线段树来模拟费用流的增广，这里显然是用堆。
我们考虑把餐厅和送餐员放在一起按照坐标排序，从前往后考虑，当考虑到一名送餐员 i i i时，我们先让它与前面的一个空的餐厅 j j j匹配。费用为 x i ? x j x_i-x_j xi??xj?，那么我们就是要找一个最小的 ? y j -y_j ?yj?。(如果没有空的餐厅我们可以视为在 ? ∞ -\infty ?∞处有无穷个餐馆)。
匹配完之后，我们可能进行调整，把这名送餐员改为匹配后面的餐厅。那么我们就可以撤销这次操作，然后把这名送餐员当做没有使用过，那么往堆中丢入 ? ( x i ? x j ) ? x i -(x_i-x_j)-x_i ?(xi??xj?)?xi?，即减去之前这组匹配的贡献，然后寻找新匹配。 扫到餐厅时也类似，先可以匹配一名送餐员，然后可以撤销这组匹配，寻找新匹配。
对所有餐厅和送餐员分别建一个堆来维护这个操作。注意我们既可以对送餐员进行反悔，也可以对餐厅进行反悔，即每新增一组匹配，我们往两个堆中分别加入反悔操作。
设每个餐厅能提供 c i c_i ci?的菜，复杂度是O ( ( n + ∑ c i ) log ? ( n + ∑ c i ) ) ((n+\sum c_i)\log (n+\sum c_i)) ((n+∑ci?)log(n+∑ci?))
这个就是一个纯模拟费用流了。
考虑这个过程中我们维护了两个堆，一个维护待匹配的送餐员，一个维护待匹配的餐厅。之前复杂度不对的原因是送餐员堆的复杂度没有保证，因为一个餐厅匹配了一名送餐员之后，这名送餐员可能反悔，所以这名送餐员又会重新丢入送餐员堆中。
但注意到对于送餐员 x , y x,y x,y和餐厅 a , b a,b a,b来说，若 x < y < a < b x< y< a< b x 复杂度就是 O ( n log ? n ) O(n\log n) O(nlogn)的了。
【【堆模拟费用流增广】UOJ455 [UER #8] 雪灾与外卖】【参考代码】

#include using namespace std; typedef long long ll; const int N=2e5+10,INF=0x3f3f3f3f; int n,m,cnt; ll ans,tot; int read() { int ret=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) ret=ret*10+(c^48),c=getchar(); return ret; }struct node { int x,w,c; node(int _x=0,int _w=0,int _c=0):x(_x),w(_w),c(_c){} bool operator <(const node&a)const{return xa.v; } }; priority_queueq1,q2; int main() { #ifndef ONLINE_JUDGE freopen("UOJ455.in","r",stdin); freopen("UOJ455.out","w",stdout); #endif n=read(); m=read(); cnt=n; for(int i=1; i<=n; ++i) a[i].x=read(); for(int i=1; i<=m; ++i) { int x=read(),w=read(),c=min(read(),n); tot+=c; if(c) a[++cnt]=node(x,w,c); } if(tot=0) break; int t=q1.top().t,res=min(c,t); q1.pop(); ans+=(ll)res*(v+w+x); q2.push(heap(-v-2*x,res)); s+=res; c-=res; t-=res; if(t) q1.push(heap(v,t)); } if(s)q1.push(heap(-w-x,s)); if(c)q2.push(heap(w-x,c)); } else { ll v=q2.top().v; int t=q2.top().t-1; q2.pop(); ans+=(ll)v+x; q1.push(heap(-v-2*x,1)); if(t)q2.push(heap(v,t)); } } printf("%lld\n",ans); return 0; }

    推荐阅读


    上一篇：【费用流】CF802C Heidi and Library (hard)

    下一篇：递推DP|Codeforces 667C Reberland Linguistics (DP)