题解 P1251 【餐巾计划问题】
Ireliaღ
2019-03-09 14:32:58
不少大佬写了zkw费用流，但由于我太菜了，不管是建图还是板子都看得我一脸蒙，所以我来说一下我的做法
首先把每一天拆成早晚两个点，然后根据题意往超级原点和汇点连边就行了，具体可以看我代码，最小费用最大流，也用的zkw费用流
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define int int64_t
//int64_t长得比long long好看
using namespace std;
const int MAXN = 2e3 + 5;
const int INF = 0x3f3f3f3f;
int n;
struct Edge{
int to, val, cost;
Edge *next, *ops;
Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};
Edge *head[MAXN << 1];
void AddEdge(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, 0, -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
namespace zkw{
int s, t, ans, res;
int dis[MAXN << 1];
bool vis[MAXN << 1];
bool Spfa() {
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
deque<int> q;
q.push_back(s);
vis[s] = true; dis[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > 0 && dis[u] + e->cost < dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] < INF;
}
int Dfs(int u, int flow) {
if (u == t) {
vis[u] = true;
res += flow;
return flow;
}
int used = 0; vis[u] = true;
for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
int v = e->to;
if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
used += mi;
}
if (used == flow) break;
}
}
return used;
}
void Work() {
res = 0; ans = 0;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof vis);
Dfs(s, INF);
}
}
}
}
signed main() {
cin >> n;
zkw :: s = 0; zkw :: t = n * 2 + 1;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
AddEdge(0, i, x, 0);//每天获得x个脏的
AddEdge(n + i, n * 2 + 1, x, 0);//每天生成x个干净的
}
int m, t1, m1, t2, m2;
cin >> m >> t1 >> m1 >> t2 >> m2;
for (int i = 1; i <= n; i++) {
if (i + 1 <= n) AddEdge(i, i + 1, INF, 0);//可以把脏的拖到第二天洗
if (i + t1 <= n) AddEdge(i, i + n + t1, INF, m1);//快洗
if (i + t2 <= n) AddEdge(i, i + n + t2, INF, m2);//慢洗
AddEdge(0, i + n, INF, m);//买新的
}
zkw :: Work();
cout << zkw :: ans << endl;
return 0;
}
```