题目描述
一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为p分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 n天(n>m),其费用为 s分(s<f)。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入格式
由标准输入提供输入数据。文件第 1 行有 1 个正整数 N，代表要安排餐巾使用计划的天数。
接下来的 N行是餐厅在相继的N天里,每天需用的餐巾数。
最后一行包含5个正整数p,m,f,n,s，p是每块新餐巾的费用; m 是快洗部洗一块餐巾需用天数; f 是快洗部洗一块餐巾需要的费用; n是慢洗部洗一块餐巾需用天数; s是慢洗部洗一块餐巾需要的费用。
输出格式
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
题目分析：
很明显是一道最小费用最大流的题目，问题在于如何建边。对于每天使用的餐巾，很明显需要拆点，分为入出两个点。所以我第一次建边时，每天从源点都建一条流量inf，费用为p的边到该天的入口，入口建一条费用为0，流量为r[i]。这部分是图代表买新纸巾所用花费。后面对于纸巾的回收清洗的建图才是最难的。
首先，毋庸置疑的是从源点到每天的出点建一条r[i]，费用为0的边，表示用过的纸巾数量。
第一次建图是，我只从出点建了边到i+m和i+n天，后面发现其实不止这两天可以用第i天的纸巾。例如，第一天纸巾需求特别大，洗的又特别快，后面所有天都可以用这天的纸巾，于是，从第i+m,i+n天分别建边到最后一天，表示该天纸巾清洗完之后所有天都可以用，但是如果n和m较小，相当于建了解决$n^{2}$条边，所以就超时了。
最后看了题解，才明白其实第i天的纸巾虽然可以清洗后在第i+m+b天使用，但可以看做是第i+b天清洗的，所以只需要将每天的出点向下一天出点建一条费用为0，流量为inf（这里不是r[i]因为可能包含前面若干天的纸巾）的边即可，表示这天用的纸巾囤积到后一天去洗，每天都有囤积，可以无限囤积下去。然后第i天往i+m和i+n天分别建流量为inf（注意，这里是inf不是r[i]，因为这里前几天的纸巾可能囤积到这里，数量较大），费用为f,s的边即可。
下面贴上代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <ll,ll> pii; #define rep(i,x,y) for(int i=x;i<y;i++) #define rept(i,x,y) for(int i=x;i<=y;i++) #define per(i,x,y) for(int i=x;i>=y;i--) #define pb push_back #define mp make_pair #define fi first #define se second #define de(x) cout<< #x<<" = "<<x<<endl #define dd(x) cout<< #x<<" = "<<x<<" " #define mes(a,b) memset(a,b,sizeof a) const ll inf= 0x3f3f3f3f; const ll maxm=5e5,maxn=5005; ll n,s,t,x,y,vol,cost,edgecount ; pii ans ; struct Edge{ ll to,vol,cost,next ; }edge[2*maxm] ; ll head[maxn],pre[maxn],path[maxn],dis[maxn] ; void insert(ll u,ll v,ll vol,ll cost) { /* dd(u); dd(v); dd(vol); de(cost); */ edge[edgecount].to = v ; edge[edgecount].vol = vol ; edge[edgecount].cost = cost ; edge[edgecount].next = head[u] ; head[u] = edgecount++ ; edge[edgecount].to = u ; edge[edgecount].vol = 0 ; edge[edgecount].cost = -cost ; edge[edgecount].next = head[v] ; head[v] = edgecount++ ; } bool spfa( ll s,ll t ) { for(int i=0;i<=n;i++) pre[ i ] = -1 ; for(int i=0;i<=n;i++) dis[ i ] = 1e9 ; dis[ s ] = 0 ; queue<ll> Q ; Q.push(s) ; while(!Q.empty()) { ll u = Q.front() ; Q.pop() ; for(ll e = head[u];e != -1 ;e = edge[e].next ) { ll v = edge[e].to ; if(edge[e].vol>0&&dis[u] + edge[e].cost < dis[v]) { dis[v] = dis[u] + edge[e].cost ; pre[v] = u ; path[v] = e ; Q.push(v) ; } } } if(pre[t]==-1) return false ; return true ; } pii mincostflow(ll s,ll t) { ll cost = 0,flow = 0 ; while(spfa(s,t)) { ll f = inf ; for(ll u = t; u != s; u = pre[u] ) if(edge[path[u]].vol < f ) f = edge[path[u]].vol ; flow+=f ; cost+= dis[t] * f ; for(ll u=t;u!=s;u=pre[u] ) { edge[path[u]].vol-=f ; edge[path[u]^1].vol+=f ; } } pii ans ; ans.first = flow ; ans.second = cost ; return ans ; } ll arrcy[2005]; ll haxi(ll day,ll x) { return n*x+day; } int main() { ios::sync_with_stdio(false); cin.tie(0); mes(head,-1); ll p,d1,c1,d2,c2; cin>>n; rept(i,1,n) cin>>arrcy[i]; cin>>p>>d1>>c1>>d2>>c2; s=0; t=2*n+1; rept(i,1,n) { insert(s,haxi(i,0),inf,p); insert(haxi(i,0),t,arrcy[i],0); insert(s,haxi(i,1),arrcy[i],0); if(i+d1<=n) insert(haxi(i,1),haxi(i+d1,0),inf,c1); if(i+d2<=n) insert(haxi(i,1),haxi(i+d2,0),inf,c2); if(i+1<=n) insert(haxi(i,1),haxi(i+1,1),inf,0); } n=2*n+2; ans=mincostflow(s,t); cout<<ans.se<<"\n"; return 0 ; }