前言
众所周知，网络流是一种可以解决多种复杂问题的算法，其核心就在于对于问题进行简化并抽象成网络流的一个个模型，再进行求解。
本篇则通过网络流24题，网络流中较为经典的题型入手，对于题目的思考过程和技巧进行分析，丰富模型并促进思维方面的提高。
网络流
0x01 P1251 餐巾计划问题
一个饭店每天要用一些餐巾，既可以买新的也可以每天晚上送去洗，洗餐巾分为快洗和慢洗，有不同的价格和时间，求最少用多少钱能满足条件。
如何判断一个题目属不属于网络流呢，从这题的角度出发，可以归纳出几个明显特征：
- 有“求最大”，“最小花费”等明显字眼
- 可以将题目中的操作简化为图中的边与点
- 有对于操作关于数量方面的限制
对于此题，既有花费最小，可简化，有数量的限制三个符合条件，我们便可以思考是否可以用网络流解答。
我们将题目所给的信息简化，将每一天变为点，输送餐巾的过程变为边，根据题中所给信息建图，尝试此种方式是否可行。失败，我们发现这种方式存在两个缺点，第一个为无法准确表示干净和脏餐巾两种状态，如将脏餐巾直接输送的话因为费用计算了两次会不如当天购买优，第二个为餐巾可以重复使用，但是网络中的流却不能复制。
分别考虑两个问题的处理方式，对于第一个，我们利用网络流建模中常用的拆点，将一天分为用前与用后两个点，避免混淆，而第二个问题我们则改变建边方法，思考题目可以得出，无论我如何变幻，每天一定会新产生 \(cost[ i ]\) 条脏餐巾，我们便将用前变为花费点，用后变为产生点，花费点既可以从源点处直接获取费用为 $ p $ 的餐巾，也可以从前几个点的产生点处“洗”来餐巾，而产生点则可以从源点处获取免费的旧餐巾（固定条数），最后再将花费点与汇点连边，由于旧餐巾是免费的的，便可以不考虑餐巾重复使用的情况。另外还需将每天的产生点与下一天的产生点连边，保证旧餐巾的延后送洗，图示如下（用 \(i\) 与 \(i+N\) 表示花费点与产生点 ）。
代码部分：
// Problem: P1251 餐巾计划问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1251
// Memory Limit: 125 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define inf 1<<30
using namespace std;
ll head[1000001],to[1000001],edg[1000001],cost[1000001],nex[1000001];
ll d[1000001],pre[1000001],incf[1000001],val[1000001],vis[1000001];
ll tot=1,s=0,t,ans;
queue<ll> q;
void add(ll u,ll v,ll c,ll w){
edg[++tot]=c;cost[tot]=w;to[tot]=v;nex[tot]=head[u];head[u]=tot;
edg[++tot]=0;cost[tot]=-w;to[tot]=u;nex[tot]=head[v];head[v]=tot;
}
bool spfa(){
for(ll i=s;i<=t;i++) d[i]=inf;
for(ll i=s;i<=t;i++) vis[i]=0;
d[s]=0;q.push(s);vis[s]=1;
incf[s]=inf;
while(q.size()){
ll u=q.front();q.pop();vis[u]=0;
for(ll i=head[u];i;i=nex[i]){
ll v=to[i];
if(!edg[i]) continue;
if(d[v]>d[u]+cost[i]){
d[v]=d[u]+cost[i];
if(!vis[v]){
q.push(v);
vis[v]++;
}
pre[v]=i;
incf[v]=min(edg[i],incf[u]);
}
}
}
if(d[t]==inf) return false;
return true;
}
void dfs(){
ll x=t;
while(x!=s){
ll i=pre[x];
edg[i]-=incf[t];
edg[i^1]+=incf[t];
x=to[i^1];
}
ans+=(d[t]*incf[t]);
}
int main(){
ll N,p,m,f,n,si;
cin>>N;
t=2*N+2;
for(ll i=1;i<=N;i++)cin>>val[i];
cin>>p>>m>>f>>n>>si;
for(ll i=1;i<=N;i++){
add(s,i,inf,p);
add(i,t,val[i],0);
add(s,i+N,val[i],0);
if(i+m<=N) add(i+N,i+m,inf,f);
if(i+n<=N) add(i+N,i+n,inf,si);
if(i+1<=N) add(i,i+1,inf,0);
}
while(spfa()) dfs();
cout<<ans;
}