网络流的应用太多了，对于各种网络流的题目，要熟练运用建模思想，将实际问题转化为网络流模型。
GO：洛谷
我们将问题划分成几个子问题：
1.“餐巾的数量”，“需要的费用”，“天数”分别指代什么？
2.快洗，慢洗会对哪些状态造成影响？
3.如何建立（记录）影响与影响间的关系
……
首先，分析题意，不难发现这是一道最小费用最大流的问题。我们按贪心的思想看，每天分配好所需要的餐巾是基本任务，而让所花的费用最小是优化方案。
因此，分配餐巾对应着网络中的流，而费用就是费用。
快洗，慢洗等状态会为未来的某一天增加餐巾，因此影响的对象是未来洗完的那一天。
我们将一天分为两个状态：消耗餐巾和送出餐巾。
消耗餐巾，在网络流中即为消耗流（使用餐巾），而送出对应着增加花费（洗餐巾），这样就将模型初步建立完成了。
而对于程序本身而言，一个流为inf的边，代表可以随便走，最终这条边也不会被删去，但是只要走过了就会消耗费用，比如将今天的餐巾送出去洗。而一个流为0，费用为0的边，可以当做一个状态的转移，比如将今天的餐巾堆积到明天，既不消耗费用也不使用餐巾。所以限制好一些条件，让程序自己完成任务即可，这是网络流最大的魅力所在。
1 #include<bits/stdc++.h> 2 #define f(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 typedef long long ll; 5 const int inf=1e9; 6 const int N=2e5+10; 7 int n,s,t,vf,tf,vs,ts,co,cnt=-1,sum; 8 int head[N],vis[N],l[N],pre[N],flow[N],dis[N]; 9 struct edge{int to,next,f,w;}e[N]; 10 void addedge(int from,int to,int f,int w){ 11 e[++cnt]=(edge){to,head[from],f,w}; head[from]=cnt; 12 } 13 queue<int> q; 14 bool spfa(){ 15 memset(vis,0,sizeof(vis)); 16 memset(dis,0x7f,sizeof(dis)); 17 dis[s]=pre[t]=0; 18 q.push(s); 19 flow[s]=inf; 20 vis[s]=1; 21 while(!q.empty()){ 22 int u=q.front(); 23 vis[u]=0; 24 for(int i=head[u];i!=-1;i=e[i].next){ 25 int v=e[i].to,f=e[i].f,w=e[i].w; 26 if(f>0&&dis[v]>dis[u]+w){ 27 dis[v]=dis[u]+w; 28 pre[v]=u; 29 l[v]=i; 30 flow[v]=min(flow[u],f); 31 if(!vis[v]){ 32 q.push(v); 33 vis[v]=1; 34 } 35 } 36 } 37 q.pop(); 38 } 39 return pre[t]; 40 } 41 void solve(){ 42 ll ansc=0; 43 while(spfa()){ 44 ansc+=flow[t]*dis[t]; 45 for(int i=t;i!=s;i=pre[i]){ 46 int ed=l[i]; 47 e[ed].f-=flow[t]; 48 e[ed^1].f+=flow[t]; 49 } 50 } 51 printf("%lld",ansc); 52 } 53 int main(){ 54 // freopen("dat.in","r",stdin); 55 memset(head,-1,sizeof(head)); 56 scanf("%d",&n); 57 t=n<<1|1;s=0; 58 f(i,1,n){ 59 scanf("%d",&sum); 60 addedge(s,i,sum,0); 61 addedge(i,s,0,0); 62 addedge(i+n,t,sum,0); 63 addedge(t,i+n,0,0); 64 } 65 scanf("%d%d%d%d%d",&co,&tf,&vf,&ts,&vs); 66 f(i,1,n){ 67 if(i+1<=n) addedge(i,i+1,inf,0),addedge(i+1,i,0,0); 68 if(i+tf<=n) addedge(i,i+n+tf,inf,vf),addedge(i+n+tf,i,0,-vf); 69 if(i+ts<=n) addedge(i,i+n+ts,inf,vs),addedge(i+n+ts,i,0,-vs); 70 addedge(s,i+n,inf,co); 71 addedge(i+n,s,0,-co); 72 } 73 solve(); 74 return 0; 75 }