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