P1251 餐巾计划问题

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = , inf = 0x3f3f3f3f;
struct Edge {
int from, to;
ll cap, flow, cost;
}; struct MCMF {
int n, m, s, t;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];
ll d[maxn];
int p[maxn];
ll a[maxn]; void init(int n) {
this->n = n;
for (int i = ; i <= n; ++i) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, ll cap, ll cost) {
edges.push_back((Edge){from, to, cap, , cost});
edges.push_back((Edge){to, from, , , -cost});
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool BellmanFord(int s, int t, ll& flow, ll& cost) {
for (int i = ; i <= n; ++i) d[i] = inf;
memset(inq, , sizeof(inq));
d[s] = ; inq[s] = ; p[s] = ; a[s] = inf; queue<int> que;
que.push(s);
while (!que.empty()) {
int u = que.front(); que.pop();
inq[u] = ;
for (int i = ; i < G[u].size(); ++i) {
Edge& e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap-e.flow);
if (!inq[e.to]) { que.push(e.to); inq[e.to] = ; }
}
}
}
if (d[t] == inf) return false;
flow += a[t];
cost += d[t] * a[t];
int u = t;
while (u != s) {
edges[p[u]].flow += a[t];
edges[p[u]^].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
ll mincost(int s, int t) {
ll flow = , cost = ;
while (BellmanFord(s, t, flow, cost));
return cost;
}
}mcmf;
int r[maxn];
int main() {
int N; scanf("%d",&N);
for (int i = ; i <= N; ++i) {
scanf("%d",&r[i]);
}
int p, m, f, n, s;
scanf("%d%d%d%d%d",&p,&m,&f,&n,&s); /// i为干净餐巾量,i+N为脏餐巾量
int be = *N+, ed = *N+;
mcmf.init(*N+);
for (int i = ; i <= N; ++i) {
/// 通过购买来获得干净餐巾
mcmf.AddEdge(be,i,r[i],p);
/// 当天的脏餐巾如何使用
mcmf.AddEdge(be,i+N,r[i],);
/// 当天的脏餐巾留到明天
if (i+ <= N) mcmf.AddEdge(i+N,(i+)+N,inf,);
/// 通过快洗部洗脏餐巾
if (i+m <= N) mcmf.AddEdge(i+N,i+m,inf,f);
/// 通过慢洗部洗脏餐巾
if (i+n <= N) mcmf.AddEdge(i+N,i+n,inf,s);
/// 使用当天的干净餐巾
mcmf.AddEdge(i,ed,r[i],);
}
ll ans = mcmf.mincost(be,ed);
printf("%lld\n",ans);
return ;
}

最新文章

  1. iOS -- CocoaPods
  2. 关于Xcode8.1 / iOS10+ 真机测试系统打印或者宏定义打印不显示问题
  3. Web语义化
  4. dtw算法
  5. Node.js 手册查询-4-Express 方法
  6. Eclipse报错:Setting property &#39;source&#39; to &#39;org.eclipse.jst.jee.server:test1&#39; did no
  7. Nim教程【三】
  8. Struts2+Uploadify文件上传使用详解
  9. VPN 隧道协议PPTP、L2TP、IPSec和SSLVPN的区别
  10. MYSQL仅仅向某个字段进行插入
  11. 原生js实现回到顶部
  12. &lt;context:property-placeholder/&gt;元素
  13. ejabberd之开题篇
  14. 《mysql必知必会》学习_第15章_20180806_欢
  15. 接口自动化&#160;基于python+Testlink+Jenkins实现的接口自动化测试框架[V2.0改进版]
  16. 第一章(欢迎进入node.js世界)
  17. shell工具-awk
  18. AngularJS学习笔记(三)数据双向绑定
  19. ASP.NetCore2.0概览
  20. Cognos11中报XQE-JDB-0004查找驱动程序类错误

热门文章

  1. 2019-2020-1 20199325《Linux内核原理与分析》第四周作业
  2. Linux C语言 检测文件是否存在
  3. Unity 极简UI框架
  4. Spring Boot中Spring data注解的使用
  5. MYSQL 索引汇总
  6. 正则表达式(grep,awk,sed)和通配符
  7. includes与indexOf
  8. PHP 面试题总结
  9. 写给MongoDB开发者的50条建议Tip21
  10. TestNG测试用例重跑详解及实践优化