Cogs 461. [网络流24题] 餐巾(费用流)

2019-11-08 01:43:11

字体：大中小

来源：转载

供稿：网友

[网络流24题] 餐巾 ★★★ 输入文件：napkin.in 输出文件：napkin.out 简单对比时间限制：5 s 内存限制：128 MB 【问题描述】一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。 (1)购买新的餐巾，每块需p分； (2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<=p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。 (3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<=f)。在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。【输入】输入文件共 3 行，第 1 行为总天数；第 2 行为每天所需的餐巾块数；第 3 行为每块餐巾的新购费用 p ，快洗所需天数 m ，快洗所需费用 f ，慢洗所需天数 n ，慢洗所需费用 s 。【输出】一行，最小的费用【样例】 napkin.in 3 3 2 4 10 1 6 2 3 napkin.out 64 【数据规模】 n<=200,Ri<=50 /*神奇的建图orz.把天拆成两个点Xi Yi.分别考虑要用餐巾和用完的餐巾.从S向Xi连一条容量为ri费用为0的边,代表每天会产生ri块旧餐巾.从Yi向T连一条容量为ri费用为0的边,代表每天需要ri块新餐巾（此边一定要填满.从Xi向Xi+1连一条容量为INF费用为0的边,代表这些旧餐巾留到下一天处理.从Xi到Yi+m连一条容量为INF,费用为f的边,代表快洗.从Xi到Yi+n连一条容量为INF,费用为s的边,代表慢洗.由S到Yi连一条容量为INF费用为p的边,代表买新的.*/#include<iostream>#include<cstdio>#include<queue>#define MAXN 4001#define INF 1e9#define LL long longusing namespace std;int n,m,p,f,s,k,cut=1,a[MAXN],S,T,head[MAXN],dis[MAXN],b[MAXN],fa[MAXN];LL ans;struct data{int u,v,next,c,f;}e[MAXN*10];queue<int>q;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}inline void add(int u,int v,int c,int f){ e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].f=f;e[cut].next=head[u];head[u]=cut; e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].f=-f;e[cut].next=head[v];head[v]=cut;}inline bool bfs(int t){ q.push(S); for(int i=1;i<=T;i++) dis[i]=INF;dis[S]=0; while(!q.empty()) { int u=q.front();q.pop();b[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]>dis[u]+e[i].f&&e[i].c) { dis[v]=dis[u]+e[i].f,fa[v]=i; if(b[v]!=t) b[v]=t,q.push(v); } } } return dis[T]!=INF;}void mincost(){ int t=1; while(bfs(t)) { int tmp=fa[T],x=INF; while(tmp) x=min(x,e[tmp].c),tmp=fa[e[tmp].u]; tmp=fa[T]; while(tmp) { e[tmp].c-=x; e[tmp^1].c+=x; tmp=fa[e[tmp].u]; } ans+=x*dis[T]; t++; } return ;}int main(){ freopen("napkin.in","r",stdin); freopen("napkin.out","w",stdout); int x,y,c,f; n=read();S=0,T=2*n+1; for(int i=1;i<=n;i++) a[i]=read(),add(S,i,a[i],0),add(i+n,T,a[i],0); p=read(),m=read(),f=read(),k=read(),s=read(); for(int i=1;i<=n;i++) { add(S,i+n,INF,p); if(i+1<=n) add(i,i+1,INF,0); if(i+m<=n) add(i,i+m+n,INF,f); if(i+k<=n) add(i,i+k+n,INF,s); } mincost(); PRintf("%lld",ans); return 0;}

上一篇：sizeof用法总结

下一篇：PAT 挖掘机技术哪家强