建图:从源点向第一层连边,第一层表示当天用掉多少餐巾,第二层表示当天需要多少餐巾,所以注意购买餐巾的边容量为无穷大,要从源点开始连向第二层的点,每天可能有剩余,在第一层内表示为流入第二天的节点。具体见代码,第一次写费用流,不知道模板对不对。。。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue> using namespace std; template<const int _n,const int _m>
struct Edge
{
struct Edge_base { int to,next,w,c; }e[_m];
int cnt,p[_n];
Edge() { clear(); }
int start(const int x) { return p[x]; }
void insert(const int x,const int y,const int z,const int zz)
{ e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; e[cnt].c=zz; p[x]=cnt; return ; }
void clear() { cnt=,memset(p,,sizeof(p)); }
Edge_base& operator[](const int x) { return e[x]; }
}; int n,Dis[],SSS,TTT,cur[],a[];
int Cost,Flow;
bool visited[];
Edge<,> e; bool Spfa(const int S)
{
int i,t,temp;
queue<int> Q;
memset(Dis,0x3f,sizeof(Dis));
Dis[S]=;
visited[S]=true;
Q.push(S);
while(!Q.empty())
{
t=Q.front(),Q.pop();visited[t]=false;
for(i=e.start(t);i;i=e[i].next)
{
temp=e[i].to;
if(e[i].w && Dis[t]+e[i].c<Dis[temp])
{
Dis[temp]=Dis[t]+e[i].c;
if(!visited[temp])
{
visited[temp]=true;
Q.push(temp);
}
}
}
}
return Dis[TTT]!=0x3f3f3f3f;
} int Dfs(const int S,const int bk)
{
if(S==TTT)return bk;
visited[S]=true;
int rest=bk;
for(int &i=cur[S];i;i=e[i].next)
{
if(!visited[e[i].to] && Dis[S]+e[i].c==Dis[e[i].to] && e[i].w)
{
int flow=Dfs(e[i].to,min(rest,e[i].w));
Cost+=flow*e[i].c;
e[i].w-=flow;
e[i^].w+=flow;
if((rest-=flow)<=)break;
}
}
if(bk==rest)Dis[S]=0x3f3f3f3f;
visited[S]=false;
return bk-rest;
} pair<int,int> Dinic()
{
while(Spfa(SSS))
{
memcpy(cur,e.p,sizeof(cur));
Flow+=Dfs(SSS,0x3f3f3f3f);
}
return make_pair(Flow,Cost);
} int main()
{
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
int i,newn,ts,cs,tf,cf; scanf("%d",&n);
for(i=;i<=n;++i)scanf("%d",&a[i]);
scanf("%d%d%d%d%d",&newn,&ts,&cs,&tf,&cf); SSS=n+n+;TTT=SSS+;
for(i=;i<=n;++i)
{
e.insert(SSS,i,a[i],),e.insert(i,SSS,,);
e.insert(i+n,TTT,a[i],),e.insert(TTT,i+n,,);
e.insert(SSS,i+n,0x3f3f3f3f,newn),e.insert(i+n,SSS,,-newn);
if(i!=n)e.insert(i,i+,0x3f3f3f3f,),e.insert(i+,i,,);
if(i+tf<=n)e.insert(i,i+tf+n,0x3f3f3f3f,cf),e.insert(i+tf+n,i,,-cf);
if(i+ts<=n)e.insert(i,i+ts+n,0x3f3f3f3f,cs),e.insert(i+ts+n,i,,-cs);
} printf("%d\n",Dinic().second); return ;
}

最新文章

  1. lua 和 c
  2. 自定义uiview 当没有数据的时候 显示自定义的uiview界面
  3. 【现代程序设计】【homework-05】
  4. poj2761Feed the dogs(划分树-区间K值)
  5. (JAVA)从零开始之--对象输入输出流ObjectInputStream、ObjectOutputStream(对象序列化与反序列化)
  6. QF——iOS沙盒机制
  7. python下使用protobuf
  8. 高速决心linux上oracle安装垃圾问题
  9. mongoDB连接数据库
  10. Binary Analysis Tool安装使用教程
  11. nginx和tomcat访问图片和静态页面的配置方法
  12. Flask初级(八)flash与前台交互get post 简介
  13. 转:JS判断值是否是数字(两种方法)
  14. KVM管理概述
  15. html5游戏开发--&quot;动静&quot;结合(二)-用地图块拼成大地图 &amp; 初探lufylegend
  16. 【原】Coursera—Andrew Ng机器学习—课程笔记 Lecture 13—Clustering 聚类
  17. BZOJ4771 七彩树(dfs序+树上差分+主席树)
  18. Elasticsearch 中文分词器IK
  19. Bitnami 2015
  20. Linux驱动多线程 - 互斥量

热门文章

  1. LVS上DR和NAT模式的缺陷
  2. thinkphp自带的验证码出现的问题
  3. C# 清除coockies
  4. promise 小抄
  5. vscode----vue中HTML代码tab键自动补全
  6. Jmeter jdbc连接
  7. dialog的各类显示方法
  8. Linq学习(零)-错误汇总
  9. python框架之虚拟环境的配置
  10. [转]STL之vector容器详解