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