poj1149PIGS

/*poj1149PIGS
每个顾客分别用一个节点来表示。
对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i ∈ [1, n)，从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为 +∞。
从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
*/

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 100000000
#define MAXN 1111
//int h[1111],u[MAXN],v[MAXN],next[MAXN],head[MAXN],w[MANX],cap[MAXN],flow[MAXN],vis[MAXN];
int h[1111],flow[MAXN][MAXN],cap[MAXN][MAXN],vis[MAXN],a[MAXN],pa[MAXN];
int n,m,k,key,lim,f;
void EK(int s,int t)
{
    queue<int> q;
    memset(flow,0,sizeof(flow));
    f=0;
    for(;;)
    {
        q.push(s);
        memset(a,0,sizeof(a));
        a[s]=INF;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int v=1;v<=n+1;v++)
            {
                if(!a[v]&&cap[u][v]>flow[u][v])
                {
                     pa[v]=u;
                     q.push(v);
                     a[v]=min(a[u],cap[u][v]-flow[u][v]);
                }
            }
        }
        if(!a[t])break;
        for(int u=t;u!=s;u=pa[u])
        {
            flow[pa[u]][u]+=a[t];
            flow[u][pa[u]]-=a[t];
        }
        f+=a[t];
    }
}

int main()
{
    
    while(scanf("%d%d",&m,&n)==2)
    {
        f=0;
        for(int i=1;i<=m;i++)scanf("%d",&h[i]);
        memset(vis,0,sizeof(0));
        for(int i=1;i<=n;i++)
        {
             scanf("%d",&k);
             for(int j=1;j<=k;j++)
             {
                 scanf("%d",&key);
                 if(!vis[key])//vis[]记录上一个打开第key个猪圈的客户
                 {
                     vis[key]=i;
                     cap[0][i]+=h[key];
                 }
                 else 
                 {
                     cap[vis[key]][i]=INF;
                     vis[key]=i;
                 }
             }
             scanf("%d",&lim);
             cap[i][n+1]=lim;
        }
        EK(0,n+1);
        printf("%d\n",f);
    }
}