|
#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;
}

|