BZOJ1221【HNOI2001】软件开发 <拆点费用流>

Problem

【HNOI2001】软件开发

Time Limit: $10 Sec$
Memory Limit: $162 MB$

Description

某软件公司正在规划一项$n$天的软件开发计划，根据开发计划第$i$天需要$n_i$个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，$A$种方式的消毒需要$a$天时间，$B$种方式的消毒需要$b$天（$b>a$），$A$种消毒方式的费用为每块毛巾$f_A$, $B$种消毒方式的费用为每块毛巾$f_B$，而买一块新毛巾的费用为$f$（新毛巾是已消毒的，当天可以使用）；而且$f>f_A>f_B$。公司经理正在规划在这$n$天中，每天买多少块新毛巾、每天送多少块毛巾进行$A$种消毒和每天送多少块毛巾进行$B$种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行$A$种消毒和多少毛巾进行$B$种消毒，使公司在这项$n$天的软件开发中，提供毛巾服务的总费用最低。

Input

第$1$行为$n,a,b,f,f_A,f_B$. 第$2$行为$n_1,n_2,\cdots,n_n$. （注：$1\le f,f_A,f_B\le 60,1\le n\le 1000$）

Output

最少费用

Sample Input

4  1  2  3  2  1
8  2  1  6

Sample Output

38

标签：拆点费用流

Solution

拆点费用流套路题
把每天拆成两个点$\frac{X_i}{Y_i}$，表示用过的毛巾和新洗好的毛巾。
建图：
$S\to X_i$ 容量$n_i$ 费用$0$
$Y_i\to T$ 容量$n_i$ 费用$0$
$S\to Y_i$ 容量$\infty$ 费用$f$
$X_i\to X_i+1$ 容量$\infty$ 费用$0$
$X_i\to Y_i+a+1$ 容量$\infty$ 费用$f_A$
$X_i\to Y_i+b+1$ 容量$\infty$ 费用$f_B$
跑小费流即可

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define MAX_M 100000
#define INF 0x7f7f7f7f
using namespace std;
int n, a, b, f, fa, fb, w[MAX_N+5];
int s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = n*2+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t]*flow;	return true;
}
int main() {
    scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &fa, &fb), init();
    for (int i = 1; i <= n; i++) scanf("%d", w+i);
    for (int i = 1; i <= n; i++) addedge(s, i, w[i], 0);
    for (int i = 1; i < n; i++) addedge(i, i+1, INF, 0);
    for (int i = 1; i <= n; i++) addedge(s, i+n, INF, f);
    for (int i = 1; i <= n; i++) addedge(i+n, t, w[i], 0);
    for (int i = 1; i < n-a; i++) addedge(i, i+a+n+1, INF, fa);
    for (int i = 1; i < n-b; i++) addedge(i, i+b+n+1, INF, fb);
    while (SPFA()) ;	return printf("%d", mic), 0;
}