題目鏈接

(bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=1920
(luogu) https://www.luogu.org/problem/P4217

題解

模擬費用流。
首先可以建出下面這樣的圖:
對于每一天\(i\)建一個點，另新建源匯\(S,T\).

(1) \(S\)向\(i\)連\((D_i,0)\) (表示訂單)

(2) \(i\)向\(i+1\)連\((+\inf,C_i)\) (拖延訂單)

(3) \(i+1\)向\(i\)連\((+\inf,M_i)\) (拖延產品相當于把訂單提前)

(4) \(i\)向\(T\)連\((U_i,P_i)\) (生產產品)
求最小費用最大流(也就是在與源點相連的邊滿流的情況下求最小費用)。

下面考慮如何模擬:
費用流的兩條重要性質——與源點相連的邊不會被退流；如果不是每次選一條全局最短路進行增廣，而是按任意順序枚舉每條和源點相連的必須流的邊進行增廣，答案也是對的。
在費用流的建圖中，我們要給每條橫向邊(\(i\)和\(i+1\)之間的邊)建立反向邊，邊權為正向邊權的相反數。
假設\(a,b\)分別為邊\(i\rightarrow i+1, i+1\rightarrow i\)的邊權，若\(i\rightarrow i+1\)的流量不為\(0\), 那么當從\(i+1\)流到\(i\)時, 找最短路就會走那條費用為\(-a\)的邊，同時給\(i\rightarrow i+1\)的流量\(-1\), 直到流量變為\(0\)為止。\(i+1\rightarrow i\)的邊同理。
在這里有一個非常妙的思路——從左往右增廣。
從左到右枚舉每個和源點相連的點，分別嘗試向左增廣和向右增廣，取代價較小者。
向右增廣時，找到這個點出發的最長路，然后計算流量為當前點剩余流量與最長路的那個點到\(T\)剩余流量的最小值。
如果我們向右增廣了\(x\)的流量，那么會導致增廣路上每個點從右往左反向邊的流量增加\(x\).
向左增廣時，因為每條橫邊有一個“閾值”，初始時為在它左邊的點向右增廣給反向邊增加的流量，流過的流量小于等于閾值時其邊權為負，大于閾值時邊權為正(注意這個閾值不同于容量，多于閾值的流完全可以流過去！我在這里錯了好幾次)，因此我們考慮在保證所有邊邊權不變的情況下一次性增廣，因此增廣的流量為當前點剩余流量、最長路的那個點到\(T\)剩余流量、當前點和最長路上點閾值的最小值三者之最小值。
如果我們向左增廣了\(x\)的流量，那么會導致增廣路上每條邊的閾值減少\(x\), 這時候如果某條邊的閾值變成了\(0\), 那么要修改這條邊的閾值。
最后，如果增廣過程中某個和\(T\)相連的點流量變為\(0\), 還要將其刪除。
所以我們要維護一個數據結構支持上述操作(具體維護方法下面再講)。
下面分析復雜度，從左往右增廣的妙處就是它能保證一條橫向邊的閾值在增廣左側的點的時候一直增加，增廣右側的點的時候一直減少，這樣跨越\(0\)的次數就是常數次，邊權變化也是常數次。
每次增廣會導致一條與源點相連的邊流完，或者一條與匯點相連的邊流完，或者一條橫向邊邊權改變，所以總操作次數為線性。

最后考慮如何用數據結構維護。
開三棵線段樹，分別維護往左增廣的費用、往右增廣的費用以及中間橫邊的流量。
第二棵線段樹，維護往右增廣的費用，由于往右增廣的邊權是不變的，因此直接維護每個點到最右邊點的從左往右邊權和即可，支持刪除(改為\(+\inf\))、查詢最小值及其位置。
第一棵線段樹也是如此，維護每個點到最左邊點的從右往左邊權和，支持修改、刪除、查詢最小值及其位置。
第三棵線段樹，維護每條橫邊的流量。首先要支持區間加、查詢最小值及其位置，然后是最棘手的操作——所有的位置初始為\(0\), 如果任何時刻任何位置經過先增加又減少之后變成了\(0\), 那么要在事件發生時快速枚舉出這些位置，并在第一棵線段樹上進行對應操作。這個我用的方法是pushdown的時候如果某個兒子區間最小值為\(0\), 那么就繼續遞歸這個兒子，直到找到葉子節點，把為零的葉子節點賦成\(+\inf\), 并在第一棵線段樹上做對應操作。但還有一個棘手的問題，就是如何區分初值\(0\)和經過修改之后先增加后減少變成了\(0\)? 我一開始使用的是如果標記的值不為\(0\)視為修改過，但是這樣是錯的，因為有可能若干次修改之后該位置上標記又變回了\(0\). 所以我又單獨記錄了一個新的標記\(f\), 表示是否修改過。當且僅當\(f\)為真且值為\(0\)時執行對應操作。

時間復雜度\(O(n\log n)\).

(我估計我的寫法又麻煩了……QAQ)

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #include<utility> #include<cassert> #define llong long long #define pli pair<llong,int> #define mkpr make_pair using namespace std;void read(int &x) {int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f; }const int N = 1e5; const llong INF = 10000000000000ll; llong a[N+3],b[N+3],w1[N+3],w2[N+3],c[N+3]; llong dl[N+3],dr[N+3]; int n;struct SegmentTree1 {struct SgTNode{llong tag; pli mini;SgTNode() {mini = mkpr(INF,0); tag = 0;}} sgt[(N<<2)+3];void update(pli &x,pli y) {if(y.first<x.first) x = y;}void pushdown(int u){assert(u<(N<<2));llong tag = sgt[u].tag;if(tag){sgt[u<<1].mini.first += tag; sgt[u<<1].tag += tag;sgt[u<<1|1].mini.first += tag; sgt[u<<1|1].tag += tag;sgt[u].tag = 0;}}void pushup(int u){assert(u<(N<<2));sgt[u].mini = mkpr(INF,0);update(sgt[u].mini,sgt[u<<1].mini);update(sgt[u].mini,sgt[u<<1|1].mini);}void build(int u,int le,int ri,llong a[]){assert(u<(N<<2));if(le==ri) {sgt[u].mini = mkpr(a[le],le); return;}int mid = (le+ri)>>1;build(u<<1,le,mid,a);build(u<<1|1,mid+1,ri,a);pushup(u);}void addval(int u,int le,int ri,int lb,int rb,llong x){assert(u<(N<<2));if(le>=lb && ri<=rb) {sgt[u].mini.first += x; sgt[u].tag += x; return;}pushdown(u);int mid = (le+ri)>>1;if(lb<=mid) addval(u<<1,le,mid,lb,rb,x);if(rb>mid) addval(u<<1|1,mid+1,ri,lb,rb,x);pushup(u);}pli querymin(int u,int le,int ri,int lb,int rb){assert(u<(N<<2));if(le>=lb && ri<=rb) {return sgt[u].mini;}pushdown(u);int mid = (le+ri)>>1; pli ret = mkpr(INF,0);if(lb<=mid) update(ret,querymin(u<<1,le,mid,lb,rb));if(rb>mid) update(ret,querymin(u<<1|1,mid+1,ri,lb,rb));pushup(u);return ret;} } sgt1,sgt2;struct SegmentTree2 {struct SgTNode{pli mini; llong tag; bool f;SgTNode() {mini = mkpr(0,0); tag = 0ll;}} sgt[(N<<2)+3];void update(pli &x,pli y) {if(y.first<x.first) x = y;}void pushup(int u){assert(u<(N<<2));sgt[u].mini = mkpr(INF,0);update(sgt[u].mini,sgt[u<<1].mini);update(sgt[u].mini,sgt[u<<1|1].mini);}void pushdown(int u,int le,int ri){assert(u<(N<<2));llong tag = sgt[u].tag;if(sgt[u].f){int mid = (le+ri)>>1;if(le!=ri){sgt[u<<1].mini.first += tag; sgt[u<<1].tag += tag; sgt[u<<1].f = true;sgt[u<<1|1].mini.first += tag; sgt[u<<1|1].tag += tag; sgt[u<<1|1].f = true;}sgt[u].tag = 0;if(sgt[u].mini.first!=0) return;if(le==ri) {sgt1.addval(1,1,n,1,le,b[le]+a[le]); sgt[u].mini.first = INF; return;}if(sgt[u<<1].mini.first==0) {pushdown(u<<1,le,mid);}if(sgt[u<<1|1].mini.first==0) {pushdown(u<<1|1,mid+1,ri);}pushup(u);}}void addval(int u,int le,int ri,int lb,int rb,llong x){assert(u<(N<<2));if(le>=lb && ri<=rb) {sgt[u].mini.first += x; sgt[u].tag += x; sgt[u].f = true; pushdown(u,le,ri); return;}pushdown(u,le,ri); int mid = (le+ri)>>1;if(lb<=mid) addval(u<<1,le,mid,lb,rb,x);if(rb>mid) addval(u<<1|1,mid+1,ri,lb,rb,x);pushup(u);}pli querymin(int u,int le,int ri,int lb,int rb){assert(u<(N<<2));if(le>=lb && ri<=rb) {return sgt[u].mini;}pushdown(u,le,ri); int mid = (le+ri)>>1; pli ret = mkpr(INF,0);if(lb<=mid) update(ret,querymin(u<<1,le,mid,lb,rb));if(rb>mid) update(ret,querymin(u<<1|1,mid+1,ri,lb,rb));pushup(u);return ret;} } sgt3;int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%lld",&w1[i]);for(int i=1; i<=n; i++) scanf("%lld",&w2[i]);for(int i=1; i<=n; i++) scanf("%lld",&c[i]);for(int i=1; i<n; i++) scanf("%lld",&b[i]);for(int i=1; i<n; i++) scanf("%lld",&a[i]);dl[1] = 0; for(int i=2; i<=n; i++) dl[i] = dl[i-1]+a[i-1];dr[n] = 0; for(int i=n-1; i>=1; i--) dr[i] = dr[i+1]-a[i];for(int i=1; i<=n; i++) dl[i]=dl[i]+c[i],dr[i]=dr[i]+c[i];sgt1.build(1,1,n,dr);sgt2.build(1,1,n,dl);for(int i=1; i<=n; i++) dl[i]-=c[i],dr[i]-=c[i];llong ans = 0ll;for(int i=1; i<=n; i++){while(w1[i]>0){pli vl = mkpr(INF,0),vr = mkpr(INF,0);pli tmp = sgt1.querymin(1,1,n,1,i);vl = mkpr(tmp.first-dr[i],tmp.second);tmp = sgt2.querymin(1,1,n,i,n);vr = mkpr(tmp.first-dl[i],tmp.second);if(vl.first<vr.first){llong flow = min(w1[i],w2[vl.second]);if(vl.second<i){tmp = sgt3.querymin(1,1,n,vl.second,i-1);flow = min(flow,tmp.first);sgt3.addval(1,1,n,vl.second,i-1,-flow);}ans += flow*vl.first;w1[i] -= flow;w2[vl.second] -= flow;if(w2[vl.second]==0){sgt1.addval(1,1,n,vl.second,vl.second,INF);sgt2.addval(1,1,n,vl.second,vl.second,INF);}}else{llong flow = min(w1[i],w2[vr.second]);ans += flow*vr.first;if(i<vr.second){sgt3.addval(1,1,n,i,vr.second-1,flow);}w1[i] -= flow;w2[vr.second] -= flow;if(w2[vr.second]==0){sgt1.addval(1,1,n,vr.second,vr.second,INF);sgt2.addval(1,1,n,vr.second,vr.second,INF);}}}if(sgt3.querymin(1,1,n,i,i).first==0){sgt3.addval(1,1,n,i,i,INF);sgt1.addval(1,1,n,1,i,b[i]+a[i]);}}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 1920 Luogu P4217 [CTSC2010]产品销售 (模拟费用流、线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。