#include<string.h>
#include<iostream>
#include<queue>
#define N 1010
using namespace std;
const int maxnode=60000;
const int maxedge=320000;
const int inf = 1 << 30;
int S,T,cnt,n,m;
int head[maxnode],gap[maxnode],pre[maxnode],cur[maxnode],dis[maxnode];
struct Edge
{
int S,t;
int next;
int w;
}st[maxedge];
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
void AddEdge(int S,int t,int w)
{
st[cnt].S=S;
st[cnt].t=t;
st[cnt].w=w;
st[cnt].next=head[S];
head[S]=cnt;
cnt++;
st[cnt].S=t;
st[cnt].t=S;
st[cnt].w=0;
st[cnt].next=head[t];
head[t]=cnt;
cnt++;
}
void bfs()
{
memset(gap,0,sizeof(gap));
memset(dis,-1,sizeof(dis));
queue<int >Q;
Q.push(T);
dis[T]=0;
gap[0]=1;
int k,t;
while(!Q.empty())
{
k=Q.front();
Q.pop();
for(int i=head[k];i!=-1;i=st[i].next)
{
t=st[i].t;
if(dis[t]==-1&&st[i^1].w>0)
{
dis[t]=dis[k]+1;
gap[dis[t]]++;
Q.push(t);
}
}
}
}
int sap()
{
int i;
for( i=S;i<=T;i++)cur[i]=head[i];
pre[S]=S;
int u=S,v;
int flow=0;
int aug=inf;
bool flag;
while(dis[S]<=T)
{
flag=false;
for( i=cur[u];i!=-1;i=st[i].next)
{
v=st[i].t;
if(st[i].w>0&&dis[u]==dis[v]+1)
{
cur[u]=i;
flag=true;
pre[v]=u;
aug=(aug>st[i].w)?st[i].w:aug;
u=v;
if(v==T)
{
flow+=aug;
for(u=pre[u];v!=S;u=pre[u])
{
v=u;
st[cur[u]].w-=aug;
st[cur[u]^1].w+=aug;
}
aug=inf;
}
break;
}
}
if(flag==true)continue;
int mint=T;
for( i=head[u];i!=-1;i=st[i].next)
{
v=st[i].t;
if(st[i].w>0&&mint>dis[v])
{
cur[u]=i;
mint=dis[v];
}
}
gap[dis[u]]--;
if(gap[dis[u]]==0)break;
gap[dis[u]=mint+1]++;
u=pre[u];
if(u==S)aug=inf;
}
return flow;
}
int main()
{
int map[N][N];
int num[N];
int f[N];
while (scanf("%d%d", &m, &n) != EOF)
{
memset(map, 0, sizeof(map));
memset(f, 0, sizeof(f));
init();
S = 0;
T = n + 1;
for (int i = 1; i <= m; ++i)
scanf("%d", &num[i]);
for (int i = 1; i <= n; ++i)
{
int a, b;
scanf("%d", &a);
for (int j = 1; j <= a; ++j)
{
int x;
scanf("%d", &x);
if (f[x] == 0)
{
map[S][i] += num[x];
f[x] = i;
}
else
{
map[f[x]][i] = inf;
f[x] = i;
}
}
scanf("%d", &b);
map[i][T] += b;
}
for (int i = S; i <= T; ++i)
for (int j = S; j <= T; ++j)
if (map[i][j])
{
//printf("%d %d %d\n", i, j, map[i][j]);
AddEdge(i, j, map[i][j]);
}
bfs();
printf("%d\n", sap());
}
}
/*
4 2
1 2 3 5
3 1 2 3 10
1 4 5
*/
|