1 /*  2 Run ID    User    Problem    Result    Memory    Time    Language    Code Length    Submit Time  3 13647887    yaodongen    1149    Accepted    260K    0MS    C++    3034B    2014-11-20 23:45:03  4 */  5 #include <iostream>  6 #include <sstream>  7 #include <ios>  8 #include <iomanip>  9 #include <functional> 10 #include <algorithm> 11 #include <vector> 12 #include <string> 13 #include <list> 14 #include <queue> 15 #include <deque> 16 #include <stack> 17 #include <set> 18 #include <map> 19 #include <cstdio> 20 #include <cstdlib> 21 #include <cmath> 22 #include <cstring> 23 #include <climits> 24 #include <cctype> 25 #define INF 0x3f3f3f3f 26 #define MP(X,Y) make_pair(X,Y) 27 #define PB(X) push_back(X) 28 #define REP(X,N) for(int X=0;X<N;X++) 29 #define REP2(X,L,R) for(int X=L;X<=R;X++) 30 #define DEP(X,R,L) for(int X=R;X>=L;X--) 31 #define CLR(A,X) memset(A,X,sizeof(A)) 32 #define IT iterator 33 #define PI 3.14159265358979323846 34 #define _ ios_base::sync_with_stdio(0);cin.tie(0); 35 #define X first 36 #define Y second 37 #define MAX_V 10101 38 #define maxn 110 39 using namespace std; 40 typedef long long ll; 41 typedef pair<int,int>PII; 42  43 struct edge{ 44     int to,cap,rev; 45     edge(int a,int b,int c):to(a),cap(b),rev(c){} 46 }; 47 vector<edge> G[maxn]; 48 int level[maxn]; 49 int iter[maxn]; 50  51 void add_edge(int from ,int to,int cap){ 52     G[from].PB(edge(to,cap,G[to].size())); 53     G[to].PB(edge(from,0,G[from].size()-1)); 54 } 55 void bfs(int s){ 56     memset(level,-1,sizeof(level)); 57     level[s]=0; 58     queue<int >que; 59     que.push(s); 60     while(!que.empty()){ 61         int u=que.front();que.pop(); 62         for(int i=0;i<G[u].size();++i){ 63             edge &e=G[u][i]; 64             if(e.cap>0 && level[e.to]<0){ 65                 level[e.to]=level[u]+1; 66                 que.push(e.to); 67             } 68         } 69     } 70 } 71 int dfs(int v,int t,int f){ 72     if(v==t) return f; 73     for(int &i=iter[v];i<G[v].size();++i){ 74         edge &e=G[v][i]; 75         if(e.cap>0 && level[e.to]>level[v]){ 76             int d=dfs(e.to,t,min(f,e.cap));         77             if(d>0){ 78                 e.cap-=d; 79                 G[e.to][e.rev].cap+=d; 80                 return d; 81             } 82         } 83     } 84     return 0; 85 } 86  87 int max_flow(int s,int t){ 88     int flow=0; 89     while(1){ 90         bfs(s); 91         if(level[t]<0) return flow; 92         memset(iter,0,sizeof(iter)); 93         int f; 94         while((f=dfs(s,t,INF))>0){ 95             flow+=f; 96         } 97     } 98 } 99 int A[1010];//猪栏中猪 100 int own[1010];101 bool used[maxn][maxn];102 int main()103 {104     //猪和顾客 105     int n,m;106     while(cin>>n>>m){107         //超级源点 超级汇点 108         int s=0,t=100+1;109         for(int i=0;i<maxn;++i)110             G[i].clear();111         for(int i=1;i<=n;++i){112             cin>>A[i];//猪栏i中猪的个数 113         }114         //最近开启猪栏的人115         memset(own,-1,sizeof(own)); 116         //是否已经建立边 117         memset(used,0,sizeof(used)); 118         for(int i=1;i<=m;++i){//第几个顾客 119             int tt;120             cin>>tt;//钥匙数 121             int temp;//猪栏的序号 122             for(int j=0;j<tt;++j){123                 cin>>temp;124                 if(own[temp]<0){//猪栏从未被打开过 125                     own[temp]=i;126                     //已经建立边，直接容量增加，不去新建边 127                     if(used[0][i]){128                         for(int k=G[0].size()-1;k>=0;--k){129                             if(G[0][k].to==i){130                                 G[0][k].cap+=A[temp];131                                 break;132                             }133                         }134                     }135                     else{136                         add_edge(0,i,A[temp]);137                         used[0][i]=1;138                     }139                 }140                 else{141                     int q=own[temp];142                     if(!used[q][i]){143                         add_edge(q,i,INF);144                         used[q][i]=1;145                     }146                     own[temp]=i;147                 }148             }149             cin>>temp;150             add_edge(i,t,temp);151         }152         cout<<max_flow(s,t)<<endl;153     }154     return 0;155 }