PIGS

Description

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

`3 33 1 102 1 2 22 1 3 31 2 6`

Sample Output

```7题意：有农民在卖猪，有M个猪笼，每个人有某些猪笼的钥匙，所以每个人可以买他能打开的猪笼中的猪，人是按顺序买猪的，当第i-1个人买完后，他能打开的猪笼可以中的猪可以被重新调整。就是在那些猪笼中移动猪。给出每个猪笼的猪数量，给出每个人能打开的猪笼序号以及想购买的猪数量。求：最多能卖多少猪。分析：主要是怎么弄让被打开过的猪笼可以移动猪。如果i跟i+1两个人的钥匙没交集，则他们只能买自己的猪笼端的猪，如果两个人有交集，那i+1的可以买i能打开的猪笼x的猪，i可以连向x，边的流量正无穷。代码：
#include <iostream>#include <stdlib.h>using namespace std;const int maxn= 20010;const int M = 1010;const __int64 inf=0x7fffffff;struct node{    __int64 v,next;    __int64 w;}fn;__int64 level[maxn],g[maxn],que[maxn],out[maxn], th, tip, visit[maxn];__int64 key[M][M], h[M], buy[M], hash[M][M], len[M];inline void add(__int64 u,__int64 v,__int64 w){    fn[th].v = v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;        fn[th].v = u, fn[th].w = 0, fn[th].next = g[v], g[v] = th++;}void build_level(__int64  n,__int64 s,__int64  e){    __int64 h=0,r=0,i,u;        for (i = 0; i <= n; i++) level[i]=0;    level[s] = 1;    que = s;    while(h <= r)    {        u = que[h++];        for (i = g[u]; i != -1; i = fn[i].next)        {            if (fn[i].w && level[fn[i].v] == 0)            {                que[++r] = fn[i].v;                level[fn[i].v] = level[u] + 1;             }        }    } }__int64 dinic(__int64 n,__int64 s,__int64 e){    __int64 ret=0,i;    while(1)    {        build_level(n,s,e);        if (level[e] == 0) break;        for (i = 0; i < n; ++i) out[i] = g[i];        __int64 q = -1;        while(1)        {            if (q < 0)            {                for (i = out[s]; i != -1; i = fn[i].next)                {                    if (fn[i].w && out[fn[i].v] != -1 && level[fn[i].v] == 2)                    {                        que[++q] = i;                        out[s] = fn[i].next;                        break;                    }                }                if (i == -1)                {                    break;                }            }            __int64 u = fn[que[q]].v;            if(u == e)            {                __int64 tmp=inf;                for(i = 0;i <= q; i++)                    if(tmp > fn[que[i]].w)tmp = fn[que[i]].w;                ret += tmp;                for(i=0;i<=q;i++)                {                    fn[que[i]].w -= tmp;                    fn[que[i]^1].w += tmp;                   }                for (i = 0; i <= q; i++)                {                    if(fn[que[i]].w == 0)                    {                        q = i-1;                        break;                    }                }            }            else            {                for (i = out[u]; i != -1; i = fn[i].next)                {                    if (fn[i].w && out[fn[i].v] !=-1 && level[u] + 1 == level[fn[i].v])                     {                        que[++q] = i, out[u] = fn[i].next;                        break;                    }                }                if(i==-1)                {                    out[u] = -1, q--;                 }                          }        }    }    return ret;}int main(){    __int64 m, n, s, t, i, j, k;    scanf("%I64d%I64d", &m, &n);    s = 0, t = n + m + 1;    for (i = 0; i < t + 10; i++)    {        g[i] = -1;    }    for (i = 1; i <= m; i++)    {        scanf("%I64d", &h[i]);        add(i + n, t, h[i]);    }    for (i = 1; i <= n; i++)    {        for (j = 1; j <= m; j++)        {            hash[i][j] = 0;        }    }    for (i = 1; i <= n; i++)    {        scanf("%I64d", &len[i]);        for (j = 0; j < len[i]; j++)        {            scanf("%I64d", &key[i][j]);            hash[i][key[i][j]] = 1;        }        scanf("%I64d", &buy[i]);        add(0, i, buy[i]);    }    for (i = 1; i <= n; i++)    {        for (j = 0; j < len[i]; j++)        {            add(i, key[i][j] + n, inf);        }        for (j = 0; j < i; j++)//对前i-1的人，有钥匙交集的，i可以买他们能打开的猪笼        {            if (i != j)            {                for (k = 0; k < len[i]; k++)                {                    if (hash[j][key[i][k]])                    {                        break;                    }                }                if (k != len[i])                {                    for (k = 0; k < len[j]; k++)                    {                        add(i, key[j][k] + n, inf);                        }                }            }        }            }    printf("%I64d\n", dinic(t + 1, s, t));    return 0;}
```