1391: [Ceoi2008]order

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

Input

第一行给出 N,M(1<=N<=1200,1<=M<=1200) 下面将有N块数据，每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序 接下来若干行每行两个数，分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000]) 最后M行，每行给出购买机器的费用(其在[1,20000]) 醉啦。。。又t又re又mle。。。人太弱。。又是一道裸题。。 

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;#define rep(i, j, k) for (int i = j; i <= k; ++i)const int maxn = +;
const int maxv = +, maxe = +;
struct MaxFlow {
    int edge, head[maxv], to[maxe], next[maxe];
    int cap[maxe];
    MaxFlow() { edge = ; memset(head, -, sizeof head); }
    void addedge(int u, int v, int c) {
        to[edge] = v, next[edge] = head[u];
        cap[edge] = c;
        head[u] = edge++;
    }
    void addEdge(int u, int v, int c) {
    //    printf("%d %d %d\n", u, v, c);
        addedge(u, v, c);
        addedge(v, u, );
    }    int s, t;
    int cur[maxv], dis[maxv], que[maxv*maxv/], front, back;    bool bfs() {
        que[front=back=] = s;
        memset(dis, INF, sizeof (int)*(t+));
        dis[s] = ;
        while (front <= back) {
            int u = que[front++];
            for (int i=head[u]; i!=-; i=next[i]) {
                if (cap[i]> && dis[to[i]]>dis[u]+) {
                    dis[to[i]] = dis[u]+;
                    que[++back] = to[i];
                }
            }
        }
        return dis[t]!=INF;
    }    int dfs(int u, int a) {
        if (u==t || a==)
            return a;
        int flow=, f;
        for (int &i=cur[u], v; i!=-; i=next[i])
            if (cap[i]> && dis[v=to[i]]==dis[u]+ && (f=dfs(v, min(a, cap[i])))>) {
                cap[i]-=f, cap[i^]+=f;
                flow+=f, a-=f;
                if (a==) break;
            }
        return flow;
    }    int MF() {
        int ret = ;
        while (bfs()) {
            memcpy(cur, head, sizeof (int) * (t+));
            ret += dfs(s, INF);
        }
        return ret;
    }
} mf;int n, m;int main() {
    scanf("%d%d", &n, &m);
    int s = , t = n+m+;
    int c, x, sum = ;
    int p, v;
    for (int i = ; i <= n; ++i) {
        scanf("%d", &c);
        sum += c;
        mf.addEdge(s, i, c);
        scanf("%d", &x);
        for (int j = ; j <= x; ++j) {
            scanf("%d %d", &p, &v);
            mf.addEdge(i, n+p, v);
        }
    }
    rep(i, , m) {
        scanf("%d", &c);
        mf.addEdge(n+i, t, c);
    }
    mf.s = s, mf.t = t;
    printf("%d\n", sum-mf.MF());    return ;
}