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

Problem

【HNOI2001】软件开发

Time Limit:
Memory Limit:

Description

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

Input

第行为. 第行为. （注：）

Output

最少费用

Sample Input

1 2	4 1 2 3 2 1 8 2 1 6

Sample Output

标签：拆点费用流

Solution

拆点费用流套路题
把每天拆成两个点，表示用过的毛巾和新洗好的毛巾。
建图：
容量费用
容量费用
容量费用
容量费用
容量费用
容量费用
跑小费流即可

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;
}