P1251 餐巾计划问题

P1251 餐巾计划问题

题目比较繁琐，也不好想，这里直接给出建图方法。

拆点，拆为起点和终点，起点的餐巾是旧餐巾，终点的餐巾是新餐巾。对于每一天，从源点连向其起点，流量为所需要的餐巾数，表示每天要处理的旧餐巾数；从终点连向汇点，流量为所需要的餐巾数，表示使用的新餐巾的数量（即每天，从源点获得了旧餐巾，将新餐巾带走）。从源点连向其终点，流量为 $inf$ ，代价为新买餐巾的代价。如果还有下一天，则该天的新餐巾可以转化为下一天的旧餐巾，连边；如果还有快洗完成的一天，就可以将该天的新餐巾转化为快洗完成的那一天的旧餐巾，同时有相应的代价。慢洗同理。

有一点，很多题解忽略了，就是费用流中的流量问题：如何保证最小费用是最大流？可以发现，最大流的情况即所有连向汇点的流量跑满，意义为每一天都有满足条件的新餐巾转化为旧餐巾。这一题的拆点和其他题不一样，一个点的内部是没有边的，即一天的旧餐巾是不能转化为一天的新餐巾。所以一天的新餐巾的来源：洗的和购买的，而当洗的不够时，为了保证最大流，会从源点获得洗的，从而保证了答案的正确性。

查看代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define INF LLONG_MAX
using namespace std;
const int N = 4e3 + 10, M = 2e5 + 10;
bool vis[N];
int idx = -1, hd[N], nxt[M], edg[M];
int n, st, ed, p, fastt, fastf, slowt, slowf, pre[N];
long long r[N], d[N], incf[N], wt[M], f[M];
bool spfa()
{
    for (int i = st; i <= ed; i++)
        incf[i] = 0;
    for (int i = st; i <= ed; i++)
        d[i] = INF;
    incf[st] = INF;
    d[st] = 0;
    queue <int> q;
    q.push(st);
    vis[st] = true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[t] + f[i] < d[edg[i]] && wt[i])
            {
                d[edg[i]] = d[t] + f[i];
                pre[edg[i]] = i;
                incf[edg[i]] = min(wt[i], incf[t]);
                if (!vis[edg[i]])
                {
                    vis[edg[i]] = true;
                    q.push(edg[i]);
                }
            }
    }
    return incf[ed] > 0;
}
long long ek()
{
    long long res = 0;
    while (spfa())
    {
        long long t = incf[ed];
        res += t * d[ed];
        for (int i = ed; i != st; i = edg[pre[i] ^ 1])
        {
            wt[pre[i]] -= t;
            wt[pre[i] ^ 1] += t;
        }
    }
    return res;
}
void add(int a, int b, long long c, long long d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    f[idx] = d;
}
int main()
{
    cin >> n;
    st = 0;
    ed = n << 1 | 1;
    for (int i = st; i <= ed; i++)
        hd[i] = -1;
    for (int i = 1; i <= n; i++)
        cin >> r[i];
    cin >> p >> fastt >> fastf >> slowt >> slowf;
    for (int i = 1; i <= n; i++)
    {
        add(st, i, r[i], 0);
        add(i, st, 0, 0);
        add(i + n, ed, r[i], 0);
        add(ed, i + n, 0, 0);
        add(st, i + n, INF, p);
        add(i + n, st, 0, -p);
        if (i < n)
        {
            add(i, i + 1, INF, 0);
            add(i + 1, i, 0, 0);
        }
        if (i + fastt <= n)
        {
            add(i, i + n + fastt, INF, fastf);
            add(i + n + fastt, i, 0, -fastf);
        }
        if (i + slowt <= n)
        {
            add(i, i + n + slowt, INF, slowf);
            add(i + n + slowt, i, 0, -slowf);
        }
    }
    cout << ek();
    return 0;
}