建图比较经典,巧妙,网络流和图论难就难在建立模型上。。。。
哎。。。。
贴个dinic模板吧。。
#include<iostream>
#define maxn 1300
#define inf 100000
using namespace std;
int f[110][110];
int d[110];
int cow[maxn];
int pre[maxn];
int N,M;
int bfs(int s)
{
int q[maxn];
q[0]=s;
memset(d,-1,sizeof(d));
d[s]=0;
int front=0,rear=1;
int j;
while(front<rear)
{
int t=q[front++];
for(j=0;j<=N+1;j++)
{
if(d[j]==-1&&f[t][j]>0)
{
d[j]=d[t]+1;
q[rear++]=j;
}
}
}
if(d[N+1]>=0)
return 1;
else return 0;
}
int dinic(int t,int sum)
{
int i;
if(t==N+1)
return sum;
int os=sum;
for(i=0;i<=N+1&∑i++)
{
if(d[i]==d[t]+1&&f[t][i]>0)
{
int a=dinic(i,min(sum,f[t][i]));
f[t][i]-=a;
f[i][t]+=a;
sum-=a;
}
}
return os-sum;
}
int main()
{
scanf("%d%d",&M,&N);
int i,j,k,l;
int tol=0;
for(i=1;i<=M;i++)
{
scanf("%d",&cow[i]);
tol+=cow[i];
}
for(i=1;i<=N;i++)
{
scanf("%d",&j);
for(l=1;l<=j;l++)
{
scanf("%d",&k);
if(pre[k]==0)
f[0][i]+=cow[k];
else
f[pre[k]][i]=tol;
pre[k]=i;
}
scanf("%d",&k);
f[i][N+1]=k;
}
int res=0;
while(bfs(0))
{
res+=dinic(0,INT_MAX);
}
printf("%d\n",res);
return 0;
}