luogu P4217 [CTSC2010]产品销售

luogu

题目给的东西可以搞成一个匹配模型,然后我们先把费用流的图建出来

• \(s->i\),流量\(d_i\),费用\(0\)
• \(i->t\),流量\(u_i\),费用\(p_i\)
• \(i->i+1\),流量\(\infty\),费用\(c_i\)
• \(i+1->i\),流量\(\infty\),费用\(m_i\)

(相当于是每个订单老鼠必须要找到对应的产品洞匹配)

然后考虑模拟费用流,如果我们从左至右枚举\(d_i\)进行增广,那么显然有两种路径,一种往左走,一种往右走,而往右走会产生一些反向弧,后面在反向弧右边增广到反向弧左边时,一定会用到这个反向弧(因为边权为负),同时往右走不会经过反向弧(因为右边还没有增广)

那么我们用线段树维护从当前点到每个点的费用,每次扫到下一个点的时候相当于把这个点连到后面的边换个方向,这就是前缀/后缀加法;还有可能要把一些向左的边临时替换成反向弧,也可以线段树区间修改;又因为反向弧是有流量限制的,就多用一个线段树维护每条反向弧剩余容量.每次找到一个费用最小的点增广,增广流量为源点出发的剩余流量、从某点到汇点的剩余流量、以及 如果向左走还有路上反向弧剩余流量 的最小值,再维护一下这个流量流过去以后产生的情况,包括有些边流满,不能用了(把边权设为\(\infty\)),反向弧出现(可以差分维护每个边上出现的反向弧容量,然后在扫到反向弧右端点后时加入向左反向弧贡献),以及反向弧流满了(去掉反向弧贡献)

#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double

using namespace std;
const int N=1e5+10;
const LL inf=1ll<<50;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
struct node
{
    LL x,p;
    bool operator < (const node &bb) const {return x<bb.x;}
}sht;
node minn(node aa,node bb){return aa<bb?aa:bb;}
struct smgttr
{
    node s[N<<2];
    LL tg[N<<2];
    void psup(int o){s[o]=minn(s[o<<1],s[o<<1|1]);} 
    void ad(int o,LL x){s[o].x+=x,tg[o]+=x;}
    void psdn(int o){if(tg[o]) ad(o<<1,tg[o]),ad(o<<1|1,tg[o]),tg[o]=0;}
    void modif(int o,int l,int r,int ll,int rr,LL x)
    {
        if(ll>rr) return;
        if(ll<=l&&r<=rr){ad(o,x);return;}
        psdn(o);
        int mid=(l+r)>>1;
        if(ll<=mid) modif(o<<1,l,mid,ll,rr,x);
        if(rr>mid) modif(o<<1|1,mid+1,r,ll,rr,x);
        psup(o);
    }
    node quer(int o,int l,int r,int ll,int rr)
    {
        if(ll>rr) return sht;
        if(ll<=l&&r<=rr) return s[o];
        psdn(o);
        node an=sht;
        int mid=(l+r)>>1;
        if(ll<=mid) an=minn(an,quer(o<<1,l,mid,ll,rr));
        if(rr>mid) an=minn(an,quer(o<<1|1,mid+1,r,ll,rr));
        psup(o);
        return an;
    }
}tr1,tr2;
int n,d[N],u[N],q[N],m[N],c[N];
LL ans,dd[N];
void bui(int o,int l,int r)
{
    if(l==r)
    {
        tr1.s[o]=(node){q[l],l};
        tr2.s[o]=(node){inf,l};
        return;
    }
    int mid=(l+r)>>1;
    bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
    tr1.psup(o),tr2.psup(o);
}

int main()
{
    sht.x=inf;
    n=rd();
    for(int i=1;i<=n;++i) d[i]=rd();
    for(int i=1;i<=n;++i) u[i]=rd();
    for(int i=1;i<=n;++i) q[i]=rd();
    for(int i=1;i<n;++i) m[i]=rd();
    for(int i=1;i<n;++i) c[i]=rd();
    bui(1,1,n);
    for(int i=1;i<n;++i)
        tr1.modif(1,1,n,i+1,n,c[i]);
    for(int i=1;i<=n;++i)
    {
        while(d[i])
        {
            node zl=tr1.quer(1,1,n,1,i-1),zr=tr1.quer(1,1,n,i,n);
            if(zl<zr)
            {
                int p=zl.p;
                node gz=tr2.quer(1,1,n,p,i-1);
                LL dt=min(1ll*min(d[i],u[p]),gz.x);
                ans+=zl.x*dt,d[i]-=dt,u[p]-=dt;
                if(!u[p]) tr1.modif(1,1,n,p,p,inf);
                if(gz.x)
                {
                    tr2.modif(1,1,n,p,i-1,-dt);
                    while(1)
                    {
                        gz=tr2.quer(1,1,n,p,i-1);
                        if(gz.x) break;
                        tr1.modif(1,1,n,1,gz.p,c[gz.p]+m[gz.p]),tr2.modif(1,1,n,gz.p,gz.p,inf);
                    }
                }
            }
            else
            {
                int p=zr.p;
                LL dt=min(d[i],u[p]);
                ans+=zr.x*dt,d[i]-=dt,u[p]-=dt;
                if(!u[p]) tr1.modif(1,1,n,p,p,inf);
                dd[i]+=dt,dd[p]-=dt;
            }
        }
        tr1.modif(1,1,n,i+1,n,-c[i]),tr1.modif(1,1,n,1,i,m[i]);
        dd[i]+=dd[i-1];
        if(dd[i])
            tr1.modif(1,1,n,1,i,-c[i]-m[i]),tr2.modif(1,1,n,i,i,-inf+dd[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

luogu P4217 [CTSC2010]产品销售

原文：https://www.cnblogs.com/smyjr/p/12210221.html