Description
Emmy在一个养猪场工作。这个养猪场有M个锁着的猪圈，但Emmy并没有钥匙。顾客会到养猪场来买猪，一个接着一个。每一位顾客都会有一些猪圈的钥匙，他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了Emmy，于是Emmy要订一个计划，使得卖出去的猪最多。 买卖的过程是这样的：一个顾客前来，并打开所有他可以打开的猪圈。然后Emmy从这些猪圈里牵出固定数目的猪卖给顾客（最多只能和顾客需要数相等），并可以重新安排这些开着的猪圈中的猪。 每个猪圈可以存放任意数目的猪。 写一个程序，使得Emmy能够卖出去尽可能多的猪。
Input
第一行有两个整数：M和N，表示猪圈数和顾客数。 第二行有M个整数，表示每个猪圈初始时有多少猪。 接下来的N行按照前来的次序描述了每一个顾客，每行的格式如下： A K1 K2…KA B A表示该顾客拥有的钥匙数，K1…KA表示每个钥匙所对应的猪圈，B表示该顾客需要购买的猪的数目。
Output
仅包含一个整数，即最多能卖出去的猪的数目。
Sample Input
3 3

3 1 10

2 1 2 2

2 1 3 3

1 2 6

Sample Output
7
HINT

1 ≤ M ≤ 1000
1 ≤ N ≤ 100

网络流建模汇总上的第一个例题。
http://wenku.baidu.com/link?url=5vBWTkDBeEKYqNiwsqWFdhL7cU-KNXgzYPKriPifFCXw8Qs8DWBrlScSSiNkFMUSGsTkuPKlePeqhlFVk62z0QoCnTKqis9oUs93FXyVjdW

直接说最后的建图过程好了，这是集训队火山爷教我的

建一个超级源点0..超级汇点n+1

以客户作为节点..

超级源点根据第一个拥有猪圈的客户和超级源点连线..容量就是第一个客户累计可以得到多少头猪..

因为第一个打开猪圈的客户可以取得所有的猪..所以超级源点和客户之间的连线容量就表示第一个打开猪圈的

人虽能够得到的数量..

然后接下来的每一个人与前一个打开猪圈的人之间连线..容量为INF..因为可以从别的猪圈调猪过来..

然后求得的最大流就是可以卖得的猪的数量..

至于为什么这么建图是正确的，证明论文里有。

//BZOJ 1280 PIGS

#include <bits/stdc++.h>
using namespace std;

const int maxn = 510;
const int maxm = 100010;
const int inf = 0x3f3f3f3f;
struct G
{
    int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
    int i, u, v, head, tail;
    for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
    qw[tail] = st;
    while(head <= tail)
    {
        u = qw[head++];
        for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
            if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
                qw[++tail] = v;
            }
        }
    }
    return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
    if(u == en || f == 0) return f;
    int flow = 0, temp;
    for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
        if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
            if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
                if(f == 0)  break;
            }
        }
    }
    return flow;
}
int dinic(int st, int en, int n)
{
    int i, ans = 0;
    while(bfs(st, en, n))
    {
        for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, inf);
    }
    return ans;
}
int pig[maxn], st, en;
int L[maxn];
vector <int> a[maxn]; //每个顾客开的猪圈
int m, n;

int main(){
    scanf("%d%d", &m,&n);
    st = 0, en = n+1;
    init();
    for(int i=1; i<=m; i++) scanf("%d",&pig[i]);
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d", &x);
        while(x--){
            scanf("%d",&y);
            a[i].push_back(y);
        }
        scanf("%d",&y);
        add(i,en,y);
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<a[i].size(); j++){
            int v=a[i][j];
            if(!L[v]){
                L[v]=i;
                add(st,i,pig[v]);
            }
            else{
                add(L[v],i,inf);
                L[v]=i;
            }
        }
    }
    int ans=dinic(st,en,en+1);
    printf("%d\n", ans);
    return 0;
}