【LG-P1251】餐巾计划问题
传送门：P1251 餐巾计划问题
一个餐厅在相继的 N 天里,每天需用的餐巾数不尽相同。假设第 i 天需要 ri 块餐巾(i = 1, 2, ..., N)。
餐厅可以购买新的餐巾,每块餐巾的费用为 p 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 n 天(n>m),其费用为 s 分(s<f)。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。
但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。\mathfrak{Solution}
费用流 + 拆点
此题的建图可以说是非常新奇了。
已知：每天早上要用或收到新的餐巾，晚上要处理脏餐巾。明显每天的早上和晚上操作不同，所以要将每天拆成两个点，早上和晚上。
- 让源点连向晚上，收到待处理脏餐巾，流量为当天使用餐巾数，费用为 0。
- 让早上连向汇点，提供当前所需净餐巾，流量为当天使用餐巾数，费用为 0。显然，当这条路流量满时，代表当天所需餐巾量已达到。
这样连接，保证了网络的联通性，同时可以在此基础上使用费用流解决此问题。
然后再来看其余四种操作：
- 快洗：因为是晚上送去白天收到使用，所以自当天晚上连向
m 天后的早上， 费用为f ，流量为inf 。 - 慢洗：同理。
- 残留餐巾：从今天晚上留到明天晚上，所以自当天晚上连向明天晚上，费用为 0，流量为
inf 。 - 购买新餐巾：自源点连向早上，费用为
p ，流量为inf 。
综上，易知当这个网络自源点向汇点连通时，满足每一天早上都有当天所需所有餐巾。所以在此基础上可以去跑费用流了。
\mathfrak{Code + Notes}
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define inf 2147483647
#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 5005;
const int maxm = 2e5 + 5;
int n, p, m, ss, f, q, s, t;
bool vis[maxn];
int incf[maxn], dis[maxn], pre[maxn], mxfl, mxcs;
int cnt = 1, hd[maxn];
struct node{
int to, nxt, flw, cst;
}e[maxm];
inline void add(int u, int v, int w, int c)
{
e[++cnt].to = v;
e[cnt].nxt = hd[u], e[cnt].flw = w, e[cnt].cst = c;
hd[u] = cnt;
e[++cnt].to = u;
e[cnt].nxt = hd[v], e[cnt].flw = 0, e[cnt].cst = -c;
hd[v] = cnt;
}
inline bool spfa()
{
queue <int> q;
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
q.push(s), vis[s] = 1, dis[s] = 0, incf[s] = 2147483647;
while(!q.empty())
{
int u = q.front();
q.pop(), vis[u] = 0;
for(int i = hd[u], v; i; i = e[i].nxt)
{
if(!e[i].flw) continue;//注意不要漏掉
if(dis[v = e[i].to] > dis[u] + e[i].cst)
{
dis[v] = dis[u] + e[i].cst;//记录一路上的费用
incf[v] = min(incf[u], e[i].flw);//最终能流到 v点的流量
pre[v] = i;//记录路径
if(!vis[v]) vis[v] = 1, q.push(v);
}
}
}
if(dis[t] != dis[n * 2 + 2]) return true;
return false;
}
inline void mcmf()
{
while(spfa())//多次增广
{
mxfl += incf[t];
mxcs += incf[t] * dis[t];
int x = t, i;
while(x != s)
{
i = pre[x];
e[i].flw -= incf[t], e[i ^ 1].flw += incf[t];
x = e[i ^ 1].to;
}
}
}
signed main()
{
/*
1.自源点向每天晚上连边 费用为 0 流量为 xi（当天使用餐巾数）
2.自每天早上向汇点连边 费用为 0 流量为 xi（当天所需餐巾数）
3.晚上快洗到若干天后早上 费用为 f 流量为 inf
4.同3，慢洗 费用为 s 流量为 inf
5.自源点向每天早上连边，买新的餐巾 费用为 p 流量为 inf
6.残留餐巾，将今天晚上向明天晚上连边 费用为 0 流量为 inf
*/
scanf("%lld", &n);
s = 0, t = n * 2 + 1;
rep(i, 1, n)
{
int x;
scanf("%lld", &x);
add(s, n + i, x, 0)/*建图 1*/, add(i, t, x, 0)/*建图 2*/;
}
scanf("%lld %lld %lld %lld %lld", &p, &m, &f, &q, &ss);
rep(i, 1, n)
{
add(s, i, inf, p);//建图 5
if(i < n) add(n + i, n + i + 1, inf, 0);//建图 6
if(i + m <= n) add(n + i, i + m, inf, f);//建图 3
if(i + q <= n) add(n + i, i + q, inf, ss);//建图 4
}
mcmf();
printf("%lld\n", mxcs);
return 0;
}——