P1251 餐巾计划问题（拆点）
最小总花费，因为\(ri<=10000000\)，排除动规，考虑网络流。因为有两个变量，时间与金钱，所以考虑费用流。
思考建图：
\(1\)、因为餐巾分为干净的餐巾和肮脏的餐巾，所以考虑拆点，将\(a_i\)拆成\(a_i\)和\(a_{i+N}\)分别表示第\(i\)天的白天和晚上，每天早上，我们使用干净的餐巾，每天晚上，我们得到肮脏的餐巾。
\(2\)、考虑将肮脏的餐巾送到快洗部，连一条\(a_{i+N}->a_{i+m}\)费用为\(f\)，流量为\(\inf\)的边
\(3\)、考虑将肮脏的餐巾送到慢洗部，连一天\(a_{i+N}->a_{i+n}\)费用为\(s\)，流量为\(\inf\)的边
\(4\)、因为我们若将肮脏的餐巾送到慢洗部和快洗部，根据网络流本质上是贪心算法，所以我们要按照他的性质来进行下列造作
\(5\)、因为无论送到快洗部还是慢洗部，洗完之后根据贪心一定会使用（不然洗来干嘛），但有些时候我们洗完之后不一定要今天使用，考虑干净的餐巾可以留到下一天，连一条\(a_{i}->a_{i+1}\)费用为\(0\)，流量为\(\inf\)的边
\(6\)、考虑买新的餐巾，因为所有的餐巾来自商店，所以定义源点为商店，每一天的早上可以从商店购买新毛巾，即连一条\(st->a_i\)费用为\(p\)，流量为\(\inf\)的边
\(7\)、第七条要和第八条一起看，使用干净的餐巾，因为每天都要使用餐巾，所以考虑连一条\(a_i->en\)（即汇点）费用为\(0\),流量为当天使用毛巾数量的边，表示当天使用了这么多条毛巾
\(8\)、因为晚上一定会得到当天的脏毛巾，但是白天的毛巾已经到达了汇点，所以我们可以直接从源点连一条\(st->a_{i+N}\)费用为\(0\),流量为当天使用毛巾数量的边，这些脏毛巾不用计算在第\(i\)天晚上前花费的钱，因为花费的钱在第\(i\)天早上就已经计算过了
\(9\)、优化一下，记录一下每个点的\(pre\)，计算费用时用\(O(N)\)计算，其他跟费用流无异
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=4e5+50,INF=1e15;
ll n,a[N],m,t1,m1,m2,t2;
ll st,en,ret,s,t;
struct jgt
{
ll to;
ll w;
ll cost;
ll ne;
}e[N];
ll h[N],idx=1,pre[N];
void add(ll x,ll y,ll z,ll c)
{
e[++idx].to=y;
e[idx].w=z;
e[idx].cost=c;
e[idx].ne=h[x];
h[x]=idx;
e[++idx].to=x;
e[idx].w=0;
e[idx].cost=-c;
e[idx].ne=h[y];
h[y]=idx;
}
ll dis[N],cj[N],pos[N];
bool vis[N];
bool spfa()
{
for(ll i=0;i<=2*n+1;i++) dis[i]=INF;
queue<ll> q;
q.push(s);
dis[s]=0,vis[s]=1;
cj[s]=INF;
while(!q.empty())
{
ll wz=q.front();
q.pop(),vis[wz]=0;
for(ll i=h[wz];i;i=e[i].ne)
{
ll j=e[i].to;
if(e[i].w&&dis[j]>dis[wz]+e[i].cost)
{
dis[j]=dis[wz]+e[i].cost;
pre[j]=wz,pos[j]=i;
cj[j]=min(cj[wz],e[i].w);
if(!vis[j]) q.push(j),vis[j]=1;
}
}
}
return dis[t]!=INF;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%lld %lld %lld %lld %lld",&m,&t1,&m1,&t2,&m2);
//i为第i天早上，i+n为第i天晚上
st=0,en=2*n+1;
s=st,t=en;
for(ll i=1;i<=n;i++)
{
if(i==1) add(st,i,INF,m);
else add(i-1+n,i,INF,m);
add(i,en,a[i],0);
add(st,i+n,a[i],0);
if(i+1<=n) add(i,i+1,INF,0);
if(i+t1<=n) add(i+n,i+t1,INF,m1);
if(i+t2<=n) add(i+n,i+t2,INF,m2);
}
while(spfa())
{
ret+=cj[t]*dis[t];
for(ll i=en;i!=st;i=pre[i])
{
e[pos[i]].w-=cj[t];
e[pos[i]^1].w+=cj[t];
}
}
printf("%lld\n",ret);
return 0;
}