P4217 [CTSC2010] 产品销售 题解

Acoipp · 2023-12-23 12:03:04 · 题解

分析

首先如果 n 没有这么大的话我们可以用费用流解决，大概就是建立 4 层点，源点单独在第一层，汇点单独在最后一层。

第二层建立 n 个节点代表第 i 天的生产，第三层建立 n 个节点代表第 i 天的任务，那么由源点向第二层连容量 u_i，费用 p_i 的边，第二层的第 i 个点向下一个点连容量无限大，费用 m_i 的边，并且连向第三层第 i 个点，容量无限大，费用为 0。

同时，为了简化我们后面的讨论，让第三层的点向第二层的点分别连接容量无限大，费用 0 的边，容易发现，这样不影响答案。

第三层的第 i 个点连向上一个点，容量无限大，费用 c_{i-1}，并且向汇点连接一条容量为 d_i，费用为 0 的边，图就构好了。

最后的图的形态像一个灯笼，如下所示：

优化

直接跑最小费用最大流会超时，我们考虑用数据结构模拟一下费用流。

我们可以枚举连向 t 的边，依次给这些边寻找一个增广路，以上图中的 8 \to t 为例，如果我们选择从 3 \sim 5 号点找增广路，那不论怎样，增广的权值都是可以用前缀和算的，即第三层的一段连续的边，第二层因为我们是按照 6 \sim 10 的顺序枚举增广边，所以 3 后面的边一定不会有可以反悔的边。

还可以由 1 \sim 3 来找对于 8 的增广路，这样的话如果第二层的边所对应的第三层的边有反悔边，那我们肯定去走第三层的边，因为其边权为负数，否则走第二层的边，那么增广的权值也可以计算，增广的流量大小就是源点出来的边的流量，汇点接收的边的流量和中间反悔边的流量取 \min 就可以了。

那么我们可以用几个线段树实现此过程，细节很多，这里就不一一展开了。

时间复杂度

容易发现如果我们是从这个点的后面找增广路，因为没有反悔边，所以要么源点出去的某条边满流，要么这个点到汇点的边满流。

如果我们从这个点前面找增广路，每次会有至少一条反悔边或者源点出去的某条边或者到汇点的边满流，而每条反悔边只会满流一次，不可能退流，故操作总数量是 O(n) 的，每次维护增广路用线段树是 O(\log n) 的，故总时间复杂度是 O(n \log n) 的。

代码

最后贴一下很丑陋的代码。

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define inf 10000000000000ll
#define N 100005
using namespace std;
ll n,d[N],u[N],p[N],m[N],c[N],i,ans,used,oth,temp;
struct node{
    ll tr[N<<2],tr2[N<<2],la[N<<2],a[N],ans,ans2;
    inline void pushup(ll p){
        if(tr[2*p]<=-inf){
            tr[p]=tr[2*p+1],tr2[p]=tr2[2*p+1];
            return ;
        }
        if(tr[2*p+1]<=-inf){
            tr[p]=tr[2*p],tr2[p]=tr2[2*p];
            return ;
        }
        if(tr[2*p]<tr[2*p+1]) tr[p]=tr[2*p],tr2[p]=tr2[2*p];
        else tr[p]=tr[2*p+1],tr2[p]=tr2[2*p+1];
    }
    inline void pushtag(ll p,ll c){la[p] += c,tr[p] += c;}
    inline void pushdown(ll p){pushtag(2*p,la[p]),pushtag(2*p+1,la[p]),la[p]=0;}
    inline void build(ll s,ll t,ll p){
        if(s==t){
            tr[p] = a[s],tr2[p] = s;
            return ;
        }
        build(s,(s+t)/2,2*p),build((s+t)/2+1,t,2*p+1);
        pushup(p);
    }
    inline void add(ll x,ll c,ll s,ll t,ll p){
        if(s==t){
            tr[p] = c,tr2[p] = s,a[s] = c;
            return ;
        }
        pushdown(p);
        if(x<=(s+t)/2) add(x,c,s,(s+t)/2,2*p);
        else add(x,c,(s+t)/2+1,t,2*p+1);
        pushup(p);
    }
    inline void modify(ll l,ll r,ll c,ll s,ll t,ll p){
        if(l<=s&&t<=r) return pushtag(p,c);
        pushdown(p);
        if(l<=(s+t)/2) modify(l,r,c,s,(s+t)/2,2*p);
        if(r>(s+t)/2) modify(l,r,c,(s+t)/2+1,t,2*p+1);
        pushup(p);
    }
    inline void query(ll l,ll r,ll s,ll t,ll p){
        if(s==1&&t==n) ans=-1;
        if(l<=s&&t<=r){
            if((ans==-1||tr[p]<=ans2)&&tr[p]>-inf) ans=tr2[p],ans2=tr[p];
            return ;
        }
        pushdown(p);
        if(l<=(s+t)/2) query(l,r,s,(s+t)/2,2*p);
        if(r>(s+t)/2) query(l,r,(s+t)/2+1,t,2*p+1);
    }
}tr1,tr2,tr3,tr4;
set<ll> add,del;
mt19937 rnd(time(0));
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(i=2;i<=n;i++) del.insert(i);
    for(i=1;i<=n;i++) cin>>d[i];
    for(i=1;i<=n;i++) cin>>u[i];
    for(i=1;i<=n;i++) cin>>p[i];
    for(i=2;i<=n;i++) cin>>m[i];
    for(i=2;i<=n;i++) cin>>c[i];
    for(i=2;i<=n;i++) m[i]+=m[i-1],c[i]+=c[i-1];
    for(i=1;i<=n;i++) tr1.a[i]=c[i]+p[i],tr2.a[i]=p[i]+m[n]-m[i],tr3.a[i]=-1e18,tr4.a[i]=p[i]+m[n]-m[i];
    tr1.build(1,n,1),tr2.build(1,n,1),tr3.build(1,n,1),tr4.build(1,n,1);
    for(i=1;i<=n;i++){
        while(d[i]){
            tr4.query(i,i,1,n,1),temp=tr4.ans2-p[i];
            tr1.query(i,n,1,n,1),tr1.ans2-=c[i];
            tr2.query(1,i,1,n,1),tr2.ans2-=temp;
            if(tr1.ans2<tr2.ans2){
                oth = tr1.ans,used = min(d[i],u[oth]),ans += used*tr1.ans2,d[i] -= used,u[oth] -= used;
                if(u[oth]==0){
                    tr1.add(oth,1e18,1,n,1);
                    tr2.add(oth,1e18,1,n,1);
                }
                while(1){
                    auto pos = del.upper_bound(i); 
                    if(pos==del.end()||*pos>oth) break;
                    tr2.modify(1,*pos-1,-((m[*pos]-m[*pos-1])+(c[*pos]-c[*pos-1])),1,n,1);
                    tr4.modify(1,*pos-1,-((m[*pos]-m[*pos-1])+(c[*pos]-c[*pos-1])),1,n,1);
                    tr3.add(*pos,0,1,n,1);
                    add.insert(*pos),del.erase(pos);
                } 
                if(i<oth) tr3.modify(i+1,oth,used,1,n,1);
            }
            else{
                oth = tr2.ans,used = min(d[i],u[oth]);
                if(oth<i){
                    tr3.query(oth+1,i,1,n,1);
                    if(tr3.ans!=-1&&tr3.ans2>-inf) used=min(used,tr3.ans2);
                }
                ans += used*tr2.ans2,d[i] -= used,u[oth] -= used;
                if(u[oth]==0){
                    tr1.add(oth,1e18,1,n,1);
                    tr2.add(oth,1e18,1,n,1);
                }
                if(oth<i){
                    while(1){
                        tr3.query(oth+1,i,1,n,1);
                        if(tr3.ans2!=used) break;
                        if(tr3.ans<=oth) break;
                        del.insert(tr3.ans),add.erase(tr3.ans);
                        tr2.modify(1,tr3.ans-1,((m[tr3.ans]-m[tr3.ans-1])+(c[tr3.ans]-c[tr3.ans-1])),1,n,1),tr3.add(tr3.ans,-1e18,1,n,1),tr4.modify(1,tr3.ans-1,((m[tr3.ans]-m[tr3.ans-1])+(c[tr3.ans]-c[tr3.ans-1])),1,n,1);
                    }
                    tr3.modify(oth+1,i,-used,1,n,1);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
Input:
10
1 3 3 4 3 9 3 3 2 4
8 10 9 6 5 1 9 7 2 6
1 1 4 4 7 2 2 6 7 7
3 2 5 4 9 2 7 5 3
9 4 8 7 4 4 1 4 10

Output:
176

5
10 3 6 1 10
2 5 8 8 9
10 9 3 10 7
7 6 3 7
10 3 9 5

20
5 6 4 10 2 9 1 10 3 4 6 4 2 1 1 5 2 7 1 8
4 2 4 8 10 10 3 5 8 3 5 5 5 6 6 4 8 4 8 5
2 4 6 7 5 6 8 1 6 6 4 3 10 10 3 5 2 9 8 6
6 6 6 1 3 1 4 5 6 2 9 3 10 4 8 3 3 2 5
2 10 8 7 6 9 6 9 10 6 10 9 1 10 1 5 7 7 10

10
8 3 3 6 2 1 5 1 9 6
8 6 6 1 8 9 4 1 4 9
9 10 4 7 4 4 1 1 8 10
1 7 8 5 10 3 6 8 2
2 8 5 3 4 2 4 8 2
*/