【学术篇】网络流24题--餐巾计划问题

传送门：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);}