|
|
 #include <iostream>
using namespace std;
#define N 105
int Edmonds_Karp(int g[][N],int n,int s,int t,int f[][N])
   {
 int i,j,k,c,head,tail,flow=0 ;
int r[N][N];
int prev[N],visit[N],q[N];
for(i=s;i<=t;i++)for(j=s;j<=t;j++)
  {
f[i][j]=0 ;
r[i][j]=g[i][j];
 }
while(1)
{
head=tail=0 ;
memset(visit,0,sizeof(visit));
q[tail++]=s ;
prev[s]=-1 ;
visit[s]=1 ;
while(head<tail)
{
k=q[head++];
for(i=s;i<=t;i++) //注意修改
if(!visit[i]&&r[k][i]>0)
{
visit[i]=1 ;
prev[i]=k ;
if(i==t)goto next ;
q[tail++]=i ;
}
}
next :
if(!visit[t])break ;
for(c=INT_MAX,j=t;j!=s;j=i)
{
i=prev[j];
if(c>r[i][j])c=r[i][j];
}
for(j=t;j!=s;j=i)
{
i=prev[j];
f[i][j]+=c ;
f[j][i]=-f[i][j];
r[i][j]=g[i][j]-f[i][j];
r[j][i]=g[j][i]-f[j][i];
}
flow+=c ;
}
return flow ;
 }
int g[N][N];
int f[N][N];
int main()
{
int i,j,k,x;
int n,m;
int s,t;
scanf("%d%d",&m,&n);
int num[1005];
int ff[1005];
for(i=1;i<=m;i++)
{
scanf("%d",&num[i]);
ff[i]=0;
}
for(j=1;j<=n;j++)
{
int temp;
scanf("%d",&temp);
for(k=0;k<temp;k++)
{
scanf("%d",&x);
if(ff[x]==0)
{
g[0][j]+=num[x];
ff[x]=j;
}
else {g[ff[x]][j]=INT_MAX;ff[x]=j;}
}
scanf("%d",&temp);
g[j][n+1]=temp;
}
s=0;t=n+1;
printf("%d\n",Edmonds_Karp(g,n,s,t,f));
return 0;
}
|