题目地址：BZOJ：Problem 1391. — [Ceoi2008]order

题目描述

有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润

输入输出格式

输入格式：
第一行给出 N,M(1<=N<=1200,1<=M<=1200) 下面将有N块数据，每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序 接下来若干行每行两个数，分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000]) 最后M行，每行给出购买机器的费用(其在[1,20000])

输出格式：
最大利润

输入输出样例

输入样例#1：

2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110

输出样例#1：

50

题解

如果没有借机器这个项目，本题就是个裸的最大权闭合子图问题。
下面考虑借机器怎么来操作。我们之前的模型是通过割机器-汇点的边来表示购买机器，这条边只能割一次，能不能找到一种边使得每进行涉及该机器的任务的时候都会被割一次。此时我们想到了原来任务-机器之间的无限流的边，只要将这条边的容量设置为借机器的费用，割这条边的时候就代表了借了一次机器。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 5];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(level[v] == -1 && gra[i].cap > 0) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || left <= 0) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(left <= 0) return flow;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int n, m, prof, tc, borr, borc, buyc, S, T, ans;

// 1 ~ n task
// n+1 ~ n+m machine

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        prof = readint(); tc = readint();
        ans += prof;
        addedge(S, i, prof);
        while(tc--) {
            borr = readint(); borc = readint();
            addedge(i, borr + n, borc);
        }
    }
    for(int i = 1; i <= m; i++) {
        buyc = readint();
        addedge(i + n, T, buyc);
    }
    ans -= dinic(S, T);
    printf("%d", ans);
    return 0;
}