傳送門(mén)：luogu2776 餐巾計(jì)劃問(wèn)題

挑戰(zhàn)之傳送門(mén)：luogu1251 餐巾

這題非常經(jīng)典啊。。不過(guò)還是要吐槽一下luogu1251喪心病狂的數(shù)據(jù)，我3s竟然TLE了，我覺(jué)得得花式壓壓常了，但是在luogu2776A了，本蒟蒻就勉強(qiáng)貼過(guò)來(lái)了。

題目大意你們點(diǎn)傳送門(mén)進(jìn)去看就好。。

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

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

1）從S向每個(gè)Xi建一條容量為∞，費(fèi)用為0的邊做限制；

2）從每個(gè)Yi向T建一條容量為ri，費(fèi)用為0的邊，表示每天要用ri的餐巾；

3）從S向每個(gè)Yi建一條容量為∞，費(fèi)用為p的邊，表示買(mǎi)餐巾；

4）從每個(gè)Xi向Xi+1建一條容量為∞，費(fèi)用為0的邊，表示延時(shí)送洗；

5）從每個(gè)Xi向Yi+m建一條容量為∞，費(fèi)用為s的邊，表示快洗；

6）從每個(gè)Xi向Yi+n建一條容量為∞，費(fèi)用為t的邊，表示慢洗。

*變量說(shuō)明：S-源點(diǎn) Xi-第i天的舊餐巾 Yi-第i天的新餐巾 T-匯點(diǎn) p-每張餐巾的費(fèi)用 m-快洗的天數(shù) s-快洗的費(fèi)用 n-慢洗的天數(shù) t-慢洗的費(fèi)用

然后裸跑費(fèi)用流就行了……我直接上板子，結(jié)果T了是什么鬼。。

個(gè)人認(rèn)為以上建邊中的1）不是很好理解。。開(kāi)始的時(shí)候覺(jué)得是新餐巾用完之后要建一條向Xi的邊，結(jié)果連樣例都過(guò)不了……桑心。不過(guò)自己畫(huà)畫(huà)圖手玩以下就發(fā)現(xiàn)這樣搞退流什么的就會(huì)出現(xiàn)問(wèn)題，所以要像1）那樣建。。

以下是代碼：

//開(kāi)發(fā)環(huán)境: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);}