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
S向每个猪圈连容量a[i]的边
每个人向T连要买猪数量的边
接下来是重点 每个人有许多猪圈钥匙 如果一把钥匙对应的猪圈被别人开了 那么向前一个有这个猪圈钥匙的人连inf 否则 直接从对应猪圈向自己连inf

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int tot=1,head[20010],to[150010],net[150010];
int val[150010];
int s,t;
void add(int x,int y,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c;
    net[++tot]=head[y],head[y]=tot,to[tot]=x,val[tot]=0;
}
int dis[20010];
int x[100010],y[100010],len[100010];
int bfs()
{
    queue<int>q;
    memset(dis,0,sizeof dis);
    q.push(s);
    dis[s]=1;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        for(int i=head[nmp];i;i=net[i])
            if(val[i]>0&&!dis[to[i]])
            {
                dis[to[i]]=dis[nmp]+1;
                q.push(to[i]);
                if(to[i]==t) return 1;
            }
    }
    return 0;
}
int dinic(int x,int flow)
{
    int tmp,temp=flow;
    if(x==t) return flow;
    for(int i=head[x];i;i=net[i])
        if(val[i]>0&&dis[to[i]]==dis[x]+1)
        {
            tmp=dinic(to[i],min(val[i],temp));
            if(!tmp) dis[to[i]]=0;
            temp-=tmp,val[i]-=tmp,val[i^1]+=tmp;
            if(!temp) break;
        }
    return flow-temp;
}
int a[1000];
int last[1000];
int main()
{
    scanf("%d%d",&m,&n);
    s=0,t=n+m+1;
    for(int i=1;i<=m;i++) scanf("%d",&a[i]),add(s,i,a[i]);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            int y;
            scanf("%d",&y);
            if(last[y]) add(last[y]+m,i+m,1<<30);
            else add(y,i+m,1<<30);
            last[y]=i;
        }
        scanf("%d",&x);
        add(i+m,t,x);
    }
    int ans=0;
    while(bfs()) ans+=dinic(s,1<<30);
    printf("%d",ans);
}