题目链接：http://poj.org/problem?id=1149
题目大意
题目意思有些鬼畜我感觉，
大体意思就是：有个访客序列，
每个访客可以打开指定的猪圈序列，
然后对于当前已经打开的猪圈其猪的个数可以任意分配，
每个访客固定要拿走指定头猪，
问最多可以有多少头猪可以被拿走。
题目分析
网络流建模问题，增加源点指向猪圈，这道题建模的关键在于
是选择选取猪圈为点还是访客，如果我们尝试以猪圈我们会发现没有办法
约束若干猪圈与源点和汇点的关系，所以我们选择访客，
访客到汇点之间直接连需求容量的边，如果该访客所要访问的猪圈
没有被打开过，那么直接从源点连以实际猪数量为容量的边过来，
如果已经被打开过那么连一条边从上一个访问的人出发到到当前访客，
容量无限表示任意分配。
网络流本质还是约束关系找准吧，这道题我也是参考了题解的思想T_T。。。
至此建模完成直接在这个图上跑Dinic即可。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
//#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
const int maxm=5e2+5;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
题目意思有些鬼畜我感觉，
大体意思就是：有个访客序列，
每个访客可以打开指定的猪圈序列，
然后对于当前已经打开的猪圈其猪的个数可以任意分配，
每个访客固定要拿走指定头猪，
问最多可以有多少头猪可以被拿走。题目分析：
网络流建模问题，增加源点指向猪圈，这道题建模的关键在于
是选择选取猪圈为点还是访客，如果我们尝试以猪圈我们会发现没有办法
约束若干猪圈与源点和汇点的关系，所以我们选择访客，
访客到汇点之间直接连需求容量的边，如果该访客所要访问的猪圈
没有被打开过，那么直接从源点连以实际猪数量为容量的边过来，
如果已经被打开过那么连一条边从上一个访问的人出发到到当前访客，
容量无限表示任意分配。
网络流本质还是约束关系找准吧，这道题我也是参考了题解的思想T_T。。。
至此建模完成直接在这个图上跑Dinic即可。
*/int m,n,k,S,T;
struct node{int u,nxt,flow;
}e[maxn];
int head[maxm],tot=0;
void init(){mst(head,-1),tot=0;
}
void add(int x,int y,int v){e[tot].u=y,e[tot].nxt=head[x],e[tot].flow=v;head[x]=tot++;e[tot].u=x,e[tot].nxt=head[y],e[tot].flow=0;head[y]=tot++;
}
int d[maxm];
bool bfs(){mst(d,-1),d[S]=0;queue<int> p;p.push(S);while(!p.empty()){int x=p.front();p.pop();for(int i=head[x];~i;i=e[i].nxt){int y=e[i].u;if(e[i].flow&&d[y]==-1){d[y]=d[x]+1;p.push(y);if(y==T) return true;}}}return false;
}
int dfs(int x,int all){if(x==T) return all;int cost=0;for(int i=head[x];~i;i=e[i].nxt){int y=e[i].u;if(e[i].flow&&d[y]==d[x]+1){int tmp=dfs(y,min(e[i].flow,all-cost));e[i].flow-=tmp;e[i^1].flow+=tmp;cost+=tmp;if(cost==all) break;}}///if(cost==0) d[x]=-1;return cost;
}
int dinic(){int ret=0;while(bfs()) ret+=dfs(S,INF);return ret;
}
int pre[maxm],a[maxm];///上一个出现的
int main(){while(~scanf("%d%d",&m,&n)){S=n+1,T=S+1;init();mst(pre,0);rep(i,1,m+1) scanf("%d",&a[i]);rep(i,1,n+1){int k,x;scanf("%d",&k);rep(j,0,k){scanf("%d",&x);if(pre[x]==0) add(S,i,a[x]);else add(pre[x],i,INF);pre[x]=i;}scanf("%d",&x);add(i,T,x);}printf("%d\n",dinic());}return 0;
}