「BZOJ 3280」小 R 的烦恼 - 费用流

程设老师最近要进行一项邪恶的实验，这个实验一共持续天，第天需要个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了所大学，第所大学共有个研究生，同时雇佣这所大学的一个研究生需要元钱。

一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生，毫无疑问，就不能再进行工作了。但是机智的老师早早联系好了家医院，第家医院医治一个濒死的研究生需要天，并且需要元钱。

链接

BZOJ 3280

题解

建立费用流模型。

为每一天建两个点，一个表示这一天开始时可用的研究生，另一个表示这一天结束时濒死的研究生。两点之间连一条边，流量上下界均为这一天所需的研究生数量，费用为零。

显然，第一天雇佣所有的研究生，每一天未使用的研究生留到下一天，和在每一天分别雇佣研究生是等价的。从源点向第一天可用研究生的点连条边，容量为，费用为一个。

从第天表示濒死的研究生的点向第天表示可用研究生的点连一条边，表示医治一些研究生，容量为正无穷，费用为。

对上下界的处理：从源点到表示每天濒死研究生的点连一条边，容量为，从表示每天可用研究生的点向汇点连一条边，容量为，最终流量为则有解。

代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>

const int MAXN = 50;
const int MAXM = 50;
const int MAXK = 50;

struct Node {
    struct Edge *e, *in;
    bool q;
    int d, f;
} N[MAXN * 2 + 2];

struct Edge {
    Node *s, *t;
    int f, c, w;
    Edge *next, *r;

    Edge(Node *s, Node *t, const int c, const int w) : s(s), t(t), f(0), c(c), w(w), next(s->e) {}
};

inline void addEdge(const int s, const int t, const int c, const int w) {
    N[s].e = new Edge(&N[s], &N[t], c, w);
    N[t].e = new Edge(&N[t], &N[s], 0, -w);
    (N[s].e->r = N[t].e)->r = N[s].e;
}

inline void edmondskarp(const int s, const int t, const int n, int &flow, int &cost) {
    flow = cost = 0;
    while (1) {
        for (int i = 0; i < n; i++) {
            N[i].in = NULL;
            N[i].q = false;
            N[i].d = INT_MAX;
            N[i].f = 0;
        }

        std::queue<Node *> q;
        q.push(&N[s]);
        N[s].d = 0, N[s].f = INT_MAX;

        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            v->q = false;

            for (Edge *e = v->e; e; e = e->next) if (e->f < e->c && e->t->d > v->d + e->w) {
                e->t->d = v->d + e->w;
                e->t->f = std::min(v->f, e->c - e->f);
                e->t->in = e;
                if (!e->t->q) {
                    e->t->q = true;
                    q.push(e->t);
                }
            }
        }

        if (N[t].d == INT_MAX) return;

        for (Edge *e = N[t].in; e; e = e->s->in) {
            e->f += N[t].f;
            e->r->f -= N[t].f;
        }

        flow += N[t].f;
        cost += N[t].f * N[t].d;
    }
}

inline void clear(const int n) {
    for (int i = 0; i < n; i++) {
        Edge *next;
        for (Edge *&e = N[i].e; e; next = e->next, delete e, e = next);
    }
}

int main() {
    int t;
    scanf("%d", &t);

    for (int i = 1; i <= t; i++) {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);

        const int s = 0, t = n * 2 + 1;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            addEdge(i, t, x, 0);
            addEdge(s, i + n, x, 0);
            sum += x;

            if (i != n) addEdge(i, i + 1, INT_MAX, 0);
        }

        for (int i = 1; i <= m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            addEdge(s, 1, a, b);
        }

        for (int i = 1; i <= k; i++) {
            int a, b;
            scanf("%d %d", &a, &b), a++;
            for (int j = 1; j <= n - a; j++) addEdge(j + n, j + a, INT_MAX, b);
        }

        int flow, cost;
        edmondskarp(s, t, n * 2 + 2, flow, cost);

        printf("Case %d: ", i);
        if (flow == sum) printf("%d\n", cost);
        else puts("impossible");

        clear(n * 2 + 2);
    }

    return 0;
}