传送门：luogu2776 餐巾计划问题
挑战之传送门：luogu1251 餐巾
这题非常经典啊。。不过还是要吐槽一下luogu1251丧心病狂的数据，我3s竟然TLE了，我觉得得花式压压常了，但是在luogu2776A了，本蒟蒻就勉强贴过来了。
（更新：luogu大牛分站提交自带O2，于是就过了~~）
题目大意你们点传送门进去看就好。。
这题分析一下就能很清晰地看出是最小费用最大流啊，不过建图比较有讲究。。
要建两排点，一排代表旧餐巾，一排代表新餐巾，然后分情况建边（*）：
1）从S向每个Xi建一条容量为∞，费用为0的边做限制；
2）从每个Yi向T建一条容量为ri，费用为0的边，表示每天要用ri的餐巾；
3）从S向每个Yi建一条容量为∞，费用为p的边，表示买餐巾；
4）从每个Xi向Xi+1建一条容量为∞，费用为0的边，表示延时送洗；
5）从每个Xi向Yi+m建一条容量为∞，费用为s的边，表示快洗；
6）从每个Xi向Yi+n建一条容量为∞，费用为t的边，表示慢洗。
*变量说明：S-源点 Xi-第i天的旧餐巾 Yi-第i天的新餐巾 T-汇点 p-每张餐巾的费用 m-快洗的天数 s-快洗的费用 n-慢洗的天数 t-慢洗的费用
然后裸跑费用流就行了……我直接上板子，结果T了是什么鬼。。
个人认为以上建边中的1）不是很好理解。。开始的时候觉得是新餐巾用完之后要建一条向Xi的边，结果连样例都过不了……桑心。不过自己画画图手玩以下就发现这样搞退流什么的就会出现问题，所以要像1）那样建。。
以下是代码：
//开发环境:dev-c++ 5.11
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXV 2005
#define MAXE 500005
#define gc getchar
#define cl(a,b) memset(a,b,sizeof(a))
#define min(a,b) (a<b?a:b)
#define INF 0x7fffffff
#define LL long long
struct edge
{
int to,next,cost,data,flow;
edge(int x,int y,int z,int zz):to(x),next(y),cost(z),data(zz),flow(0){}
edge(){}
}e[MAXE];
bool vis[MAXV];
int v[MAXV],p[MAXV],a[MAXV],d[MAXV],r[MAXV>>1];
int s,t,tot=1;
LL flow=0,cost=0;
void qin(int &a)
{
a=0;char c=gc();bool f=0;
for(;(c<'0'||c>'9')&&c!='-';c=gc());
if(c=='-') f=1,c=gc();
for(;c>='0'&&c<='9';c=gc()) a=(a<<1)+(a<<3)+c-'0';
}
void build(int x,int y,int z,int zz)
{
e[++tot]=edge(y,v[x],z,zz); v[x]=tot;
e[++tot]=edge(x,v[y],-z,0); v[y]=tot;
}
bool spfa(LL &flow,LL &cost)
{
using namespace std;
cl(d,0x7f); cl(vis,0);
d[s]=0; vis[s]=1; p[s]=0; a[s]=INF;
queue<int> q;
q.push(s);
while(!q.empty())
{
int x=q.front(); q.pop(); vis[x]=0;
for(int i=v[x];i;i=e[i].next)
if(e[i].data>e[i].flow&&d[e[i].to]>d[x]+e[i].cost)
{
d[e[i].to]=d[x]+e[i].cost;
p[e[i].to]=i;
a[e[i].to]=min(e[i].data-e[i].flow,a[x]);
if(!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;
}
}
if(d[t]==0x7f7f7f7f) return 0;
flow+=a[t]; cost+=a[t]*d[t];
for(int i=t;i-s;i=e[p[i]^1].to)
e[p[i]].flow+=a[t],e[p[i]^1].flow-=a[t];
return 1;
}
int main()
{
int N,p,kd,kf,md,mf; qin(N); s=0; t=N<<1|1;
qin(p);qin(kd);qin(kf);qin(md);qin(mf);
for(int i=1;i<=N;i++) qin(r[i]);
for(int i=1;i<=N;i++)
{
build(s,N+i,p,INF);
build(s,i,0,r[i]);
build(N+i,t,0,r[i]);
build(t,N+i,INF,0);
if(i+1<=N) build(i,i+1,0,INF);
if(i+kd<=N) build(i,N+i+kd,kf,INF);
if(i+md<=N) build(i,N+i+md,mf,INF);
}
while(spfa(flow,cost));
printf("%lld",cost);
}