bzoj1221[HNOI2001] 软件开发 - 网络流24题のNo.10餐巾问题

本文主要是介绍bzoj1221[HNOI2001] 软件开发 - 网络流24题のNo.10餐巾问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1221

题目大意：
一项n天的软件开发计划，第i天需要ni个软件开发人员，要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB。也可以买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）且f>fA>fB。求最低的总费用。

题解：
最小费用最大流
构图好厉害
把每天拆成两个点 $x_i$ 、 $y_i$ ， $x_i$ 表示第 $i$ 天用过的餐巾， $y_i$ 表示第 $i$ 天收到的干净的餐巾。
构图如下：
1、 $x_i$ -> $x_{i+1}$ ，流量为 $\infty$ ，费用为 $0$ ，用过的餐巾可以留到下一天嘛
2、 $x_i$ -> $y_{i+a+1}$ ，流量为 $\infty$ ，费用为fA，第一种消毒方式。第 $i$ 天的用完之后餐巾可以经过消毒给第i+a+1天的用。
3、同理第二种消毒方式。 $x_i$ -> $y_{i+b+1}$ ，流量为 $\infty$ ，费用为fB。
4、 $S$ -> $y_i$ ，流量为 $\infty$ ，费用为f，这个表示买毛巾，不是别的天用过的。
5、 $S$ -> $x_i$ ，流量为 $n_i$ ，费用为0； $y_i$ -> $T$ ，流量为 $n_i$ ，费用为0；这两条边就是需求的限制。要满足需求的话， $y_i$ 就一定有 $n_i$ 流出(入)， $x_i$ 就一定有 $n_i$ 流入(出)，就是说这天一定有 $n_i$ 张餐巾用过。

然后就是跑最小费用最大流了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 2500const int inf=0x7fffffff;
struct node
{int y,c,f,next,ot;//c-费用 f-流量
}a[maxn*6];int len,first[maxn];
int n,S,T,pre[maxn],l[maxn],d[maxn];
int flow[maxn];bool vis[maxn];
int mymin(int x,int y){return (x<y)?x:y;}
void ins(int x,int y,int f,int c)
{len++;int now1=len;a[len].y=y;a[len].c=c;a[len].f=f;a[len].next=first[x];first[x]=len;len++;int now2=len;a[len].y=x;a[len].c=-c;a[len].f=0;a[len].next=first[y];first[y]=len;a[now1].ot=now2;a[now2].ot=now1;
}
int head,tail,list[maxn*10];
int bfs(int st,int ed)
{head=1;tail=1;list[head]=st;memset(d,-1,sizeof(d));memset(pre,-1,sizeof(pre));memset(vis,false,sizeof(vis));pre[st]=0;d[st]=0;flow[st]=inf;vis[st]=true;while (head<=tail){int x=list[head++];for (int k=first[x];k!=-1;k=a[k].next){int y=a[k].y;if (!a[k].f) continue;if (d[y]==-1 || d[y]>d[x]+a[k].c){d[y]=d[x]+a[k].c;flow[y]=mymin(flow[x],a[k].f);pre[y]=x;l[y]=k;if (!vis[y]) {vis[y]=true;list[++tail]=y;}}}vis[x]=false;}if (pre[ed]==-1) return 0;return flow[ed];
}
int MCMF()
{int delta,ans=0;while (delta=bfs(S,T)){ans+=delta*d[T];int x=T;while (x!=S){a[l[x]].f-=delta;a[a[l[x]].ot].f+=delta;x=pre[x];}}return ans;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int ta,tb,ff,fa,fb,i,r;scanf("%d%d%d%d%d%d",&n,&ta,&tb,&ff,&fa,&fb);S=2*n+1;T=S+1;len=0;memset(first,-1,sizeof(first));for (i=1;i<=n;i++){scanf("%d",&r);ins(S,2*i-1,r,0);ins(2*i,T,r,0);if (i!=n) ins(2*i-1,2*(i+1)-1,inf,0);ins(S,2*i,inf,ff);if (i+ta+1<=n) ins(2*i-1,2*(i+ta+1),inf,fa);if (i+tb+1<=n) ins(2*i-1,2*(i+tb+1),inf,fb);}printf("%d\n",MCMF());return 0;
}