先考虑流。
(s->i)连流量(d_i)费用(0)
(i->t)连流量(u_i)费用(p_i)
(i->i+1)连流量(inf)费用(c_i)
(i+1->i)连流量(inf)费用(m_i)
然而我们并不能通过此题。
考虑从左到右枚举所有和源点连边的边进行增广。这样子的好处是不用考虑向左增广后的反向边，且时间复杂度可以保证。
我们需要找到当前边向左/右的最短路。
当前边向右的最短路：由于我们后面的边都没有增广过，所以我们一定不会走反向边。
可以用一个线段树维护，线段树的下标(x)表示当前点到(x)的最短路。如果一个点和汇点连的边代价变为(0)，需要把这条边在线段树上删除（赋值为(inf)）
当前边向左的最短路：可能会走反向边。如果一条原边被反向边覆盖，则我们一定会走这条边上的反向边。
考虑用另一个线段树维护权值和我们当前反向边的流量，线段树的下标(x)表示：
如果反向边有流量，则是反向边的流量，否则是(inf)。
每次在线段树上找到最小值的位置。然后把第二个线段树上权值为(0)的下标都赋值成(inf)，且在第一颗线段树上进行修改。
找到第二个线段树上为(0)的值可以寻找最小值。
增广流量：(min(最小值位置到t的流量,当前点到最小值位置的流量,s到当前点的流量))
维护当前点到前面是否是反向边可以用差分数组。
在当前点增广完后，使用差分数组判定当前点到前面的反向边流量。
分析复杂度：一条边在被向右增广时复杂度显然是(O(nlog_2n))
在被向左增广时，由于我们从左到右增广，所以当前边的流量显然会先增加，后减少。最终只会减到(0)一次。
而只有减到(0)才会贡献复杂度(O(log_2n))。
同时，与源点/汇点相邻的边只有减到(0)才会贡献复杂度(O(log_2n))。
所以总时间复杂度(O(nlog_2n))
代码细节较多。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n,d[N],u[N],p[N],m[N],c[N],s[N];
struct no{
int v,p;
};
int operator<(no x,no y){
return x.v<y.v;
}
struct sgt{
no a[N*4];
int tg[N*4];
void pd(int o){
if(tg[o]){
tg[o*2]+=tg[o];
tg[o*2+1]+=tg[o];
a[o*2].v+=tg[o];
a[o*2+1].v+=tg[o];
tg[o]=0;
}
}
void ad(int o,int l,int r,int x,int y,int z){
if(r<x||y<l)
return;
if(x<=l&&r<=y){
tg[o]+=z;
a[o].v+=z;
return;
}
int md=(l+r)/2;
pd(o);
ad(o*2,l,md,x,y,z);
ad(o*2+1,md+1,r,x,y,z);
a[o]=min(a[o*2],a[o*2+1]);
}
no qu(int o,int l,int r,int x,int y){
if(r<x||y<l)
return(no){1e15,0};
if(x<=l&&r<=y)
return a[o];
pd(o);
int md=(l+r)/2;
return min(qu(o*2,l,md,x,y),qu(o*2+1,md+1,r,x,y));
}
}s1,s2;
void bd(int o,int l,int r){
if(l==r){
s1.a[o]=(no){p[l],l};
s2.a[o]=(no){1e15,l};
return;
}
int md=(l+r)/2;
bd(o*2,l,md);
bd(o*2+1,md+1,r);
s1.a[o]=min(s1.a[o*2],s1.a[o*2+1]);
s2.a[o]=min(s2.a[o*2],s2.a[o*2+1]);
}
void deb(int t){
if(t==1){
for(int i=1;i<=n;i++)
printf("%lld ",s1.qu(1,1,n,i,i).v);
puts("");
}
else{
for(int i=1;i<=n;i++)
printf("%lld ",s2.qu(1,1,n,i,i).v);
puts("");
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&d[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&u[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&p[i]);
for(int i=1;i<n;i++)
scanf("%lld",&m[i]);
for(int i=1;i<n;i++)
scanf("%lld",&c[i]);
bd(1,1,n);
for(int i=1;i<n;i++)
s1.ad(1,1,n,i+1,n,c[i]);
int ans=0;
for(int i=1;i<=n;i++){
while(d[i]){
no pl=s1.qu(1,1,n,1,i),pr=s1.qu(1,1,n,i+1,n);
if(pl<pr){
int x=pl.p;
no pp=s2.qu(1,1,n,x,i);
int f=min(d[i],min(u[x],pp.v));
d[i]-=f;
u[x]-=f;
ans+=f*pl.v;
if(!u[x])
s1.ad(1,1,n,x,x,1e15);
if(pp.v){
s2.ad(1,1,n,x,i-1,-f);
while(1){
pp=s2.qu(1,1,n,x,i-1);
if(pp.v)
break;
x=pp.p;
s1.ad(1,1,n,1,x,c[x]+m[x]);
s2.ad(1,1,n,x,x,1e15);
}
}
}
else{
int x=pr.p,f=min(d[i],u[x]);
d[i]-=f;
u[x]-=f;
ans+=f*pr.v;
s[i]+=f;
s[x]-=f;
if(!u[x])
s1.ad(1,1,n,x,x,1e15);
}
}
s1.ad(1,1,n,1,i,m[i]);
s1.ad(1,1,n,i+1,n,-c[i]);
s[i]+=s[i-1];
if(s[i]){
s1.ad(1,1,n,1,i,-c[i]-m[i]);
s2.ad(1,1,n,i,i,-1e15+s[i]);
}
}
printf("%lld",ans);
}