Cogs 461. [網(wǎng)絡(luò)流24題] 餐巾(費用流)

2019-11-08 01:43:11

字體：大中小

供稿：網(wǎng)友

[網(wǎng)絡(luò)流24題] 餐巾 ★★★ 輸入文件：napkin.in 輸出文件：napkin.out 簡單對比時間限制：5 s 內(nèi)存限制：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)。在每天結(jié)束時，餐廳必須決定多少塊用過的餐巾送到快洗部，多少塊送慢洗部。在每天開始時，餐廳必須決定是否購買新餐巾及多少，使洗好的和新購的餐巾之和滿足當(dāng)天的需求量Ri，并使N天總的費用最小。【輸入】輸入文件共 3 行，第 1 行為總天數(shù)；第 2 行為每天所需的餐巾塊數(shù)；第 3 行為每塊餐巾的新購費用 p ，快洗所需天數(shù) m ，快洗所需費用 f ，慢洗所需天數(shù) n ，慢洗所需費用 s 。【輸出】一行，最小的費用【樣例】 napkin.in 3 3 2 4 10 1 6 2 3 napkin.out 64 【數(shù)據(jù)規(guī)模】 n<=200,Ri<=50 /*神奇的建圖orz.把天拆成兩個點Xi Yi.分別考慮要用餐巾和用完的餐巾.從S向Xi連一條容量為ri費用為0的邊,代表每天會產(chǎn)生ri塊舊餐巾.從Yi向T連一條容量為ri費用為0的邊,代表每天需要ri塊新餐巾（此邊一定要填滿.從Xi向Xi+1連一條容量為INF費用為0的邊,代表這些舊餐巾留到下一天處理.從Xi到Y(jié)i+m連一條容量為INF,費用為f的邊,代表快洗.從Xi到Y(jié)i+n連一條容量為INF,費用為s的邊,代表慢洗.由S到Y(jié)i連一條容量為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();