Luogu P1251. 餐巾计划问题 (Mincost Flow)

日付: 12月 06, 2018

## Problem
一个餐厅在连续的$n$天内分别需要使用$A[i]$张餐巾。不够的餐巾可以以$p$的单价购买新餐巾，或者把脏餐巾送去洗。送洗有两种方式，分别能够在$fn$天和$sn$天后送回，单价分别是$f$和$s$。要求最少费用。
## Solution
一开始想到了建这样一个图：
1. 每一天拆成早上和晚上
2. 源点向每天早上连一条容量无限费用$p$的边
3. 每天早上向晚上连一条容量$A[i]$费用为0的边
4. 每天晚上向第$fn$天后的早上连一条容量无限费用为$f$的边
5. 每天晚上向第$sn$天后的早上连一条容量无限费用为$s$的边
6. 每天晚上向下一天晚上连一条容量无限费用为0的边 (脏毛巾可以攒到第二天)

这样建图后要求#3中的边必须满流，此时最小费用流就是答案。但仅仅这样是不行的，因为图中没有汇点，无法确定费用最小时流量是多少，并且考虑下界边非常麻烦。

修改一下，把#3中的边分成两个部分， 一个是源点到晚上的流量，一个是早上到汇点的容量为$A[i]$费用为0的边，这样就转化为了最小费用最大流。其余部分的边无需改变。

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr int inv(LL x, int m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr int mpow(LL a, LL k, int m) { int r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

template <typename T> struct MinCostFlow {
    struct Edge { int u, v; T c, w, f; };
    const T eps = T(1e-9), INF = numeric_limits<T>::max();
    vector<Edge> E;
    int n, src, sink;
    vector<vector<int>> G;
    T flow = T(), cost = T();
    MinCostFlow(int n, int src, int sink): n(n), src(src), sink(sink), G(n) {}

void clear_flow() { for (auto &e : E) e.f = T(); flow = cost = T(); }
    void reduce() { for (auto &e : E) e.c -= e.f; }
    void add_edge(int u, int v, T cap, T cost) {
        assert(0 <= u && u < n && 0 <= v && v < n);
        G[u].push_back(E.size()), E.push_back({u, v, cap, cost, T()});
        G[v].push_back(E.size()), E.push_back({v, u, 0, -cost, T()});
    }
    T min_cost_flow(T f = -1) {
        if (f < 0) f = INF;
        if (flow > f) clear_flow();
        f -= flow;
        while (f > eps) {
            vector<T> D(n, INF);
            vector<int> Inq(n), P(n);
            queue<int> Q;
            Q.push(src), D[src] = T(), Inq[src] = 1;
            while (!Q.empty()) {
                int u = Q.front();
                Q.pop(), Inq[u] = 0;
                for (auto i : G[u]) {
                    const auto &e = E[i];
                    if (e.c - e.f > eps && D[e.v] > D[u] + e.w) {
                        D[e.v] = D[u] + e.w, P[e.v] = i;
                        if (!Inq[e.v]) Q.push(e.v), Inq[e.v] = 1;
                    }
                }
            }
            if (D[sink] == INF) break;
            T can = f;
            for (int u = sink; u != src; u = E[P[u]].u)
                can = min(can, E[P[u]].c - E[P[u]].f);
            f -= can, flow += can, cost += D[sink] * can;
            for (int u = sink; u != src; u = E[P[u]].u)
                E[P[u]].f += can, E[P[u] ^ 1].f -= can;
        }
        return cost;
    }
};

const int N = 2005, INF = 1 << 30;
int n, A[N], p, fn, f, sn, s;

int main() {
    scanf("%d", &n);
    FI(i, 1, n) scanf("%d", &A[i]);
    scanf("%d%d%d%d%d", &p, &fn, &f, &sn, &s);
    int src = 0, sink = 2 * n + 1;
    MinCostFlow<LL> mf(sink + 1, src, sink);
    FI(i, 1, n) {
        mf.add_edge(src, i, A[i], 0);
        mf.add_edge(n + i, sink, A[i], 0);
        if (i != n) mf.add_edge(i, i + 1, INF, 0);
        if (i + fn <= n) mf.add_edge(i, n + i + fn, INF, f);
        if (i + sn <= n) mf.add_edge(i, n + i + sn, INF, s);
        mf.add_edge(src, n + i, INF, p);
    }
    printf("%lld\n", mf.min_cost_flow());
}
```

KONGROOの基地

このブログを検索

Luogu P1251. 餐巾计划问题 (Mincost Flow)

コメント

コメントを投稿