最小割
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int inf=1000000000; int head[3003]; int to[5100010],c[5100010]; int next[5100010],q[3003]; int d[3003],a[3003],b[3003]; int n,m,num,s,t,ans,sum; void ins(int x,int y,int z){ to[++num]=y;c[num]=z;next[num]=head[x];head[x]=num; } void addedge(int x,int y,int z){ ins(x,y,z); ins(y,x,0); } bool bfs(){ for(int i=s;i<=t;i++){ d[i]=-1; } int l=0,r=1; q[1]=s;d[s]=0; while(l<r){ int x=q[++l]; for(int p=head[x];p;p=next[p]){ if(c[p]&&d[to[p]]==-1){ d[to[p]]=d[x]+1; q[++r]=to[p]; } } } if(d[t]==-1){ return 0; }else{ return 1; } } int find(int x,int low){ if (x==t||low==0){ return low; } int totflow=0; for(int p=head[x];p;p=next[p]){ if (c[p] && d[to[p]]==d[x]+1){ int a=find(to[p],min(low,c[p])); c[p]-=a; c[p^1]+=a; totflow+=a; low-=a; if(low==0){ return totflow; } } } if(low){ d[x]=-1; } return totflow; } void dinic(){ while(bfs()){ ans+=find(s,inf); } } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; sum+=b[i]; } num=1; cin>>m; s=0,t=n+2*m+1; for(int i=1;i<=n;i++){ addedge(s,i,b[i]); addedge(i,t,a[i]); } for(int i=1;i<=m;i++){ int k,x,c1,c2; cin>>k>>c1>>c2; addedge(s,n+i*2,c2); addedge(n+i*2-1,t,c1); sum+=c1+c2; for(int j=1;j<=k;j++){ cin>>x; addedge(x,n+i*2-1,inf); addedge(n+i*2,x,inf); } } dinic(); cout<<sum-ans<<endl; return 0; } /* in: 3 4 2 1 2 3 2 1 2 3 2 1 2 out: 11 */