傳送門：luogu2776 餐巾計劃問題

挑戰之傳送門：luogu1251 餐巾

這題非常經典啊。。不過還是要吐槽一下luogu1251喪心病狂的數據，我3s竟然TLE了，我覺得得花式壓壓常了，但是在luogu2776A了，本蒟蒻就勉強貼過來了。

題目大意你們點傳送門進去看就好。。

這題分析一下就能很清晰地看出是最小費用最大流啊，不過建圖比較有講究。。

要建兩排點，一排代表舊餐巾，一排代表新餐巾，然后分情況建邊（*）：

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 longstruct 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);}