题目大意：给定一些元素，需要放在两个集合里，每个元素放在集合A里的贡献为a[i]，放在集合B里的贡献为b[i]
其中还有一些子集 若一个子集的所有元素都在A集合里会获得贡献值c1[i]，都放在B集合里会获得贡献值c2[i]
首先我们先把所有的元素都放在集合A中 获得所有的a[i]和c1[i] 然后考虑最大权闭合子图
一个点如果不选就放在A集合中 选就放在B集合中
一个点如果选 那么就要扣除相应的ai并获得相应的b[i] 于是每个点的权值为b[i]-a[i]
将所有的子集拆点变成两个
一个子集中的任意一个元素选择 那么就要扣除相应的c1[i] 这个子集的权值为-c1[i] 从这个子集的所有点出发连一条到达这个点的边
一个子集中所有的元素都选择 那么就会获得相应的c2[i] 这个子集的权值为c2[i] 从这个点出发向这个子集的所有点连一条边
然后建图跑最大流即可
注意边集要足够大，开到200W才够用
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 3030
#define INF 0x3f3f3f3f
#define S 0
#define T 3010
using namespace std;
struct abcd{
int to,f,next;
}table[2002000];
int head[M],tot=1;
int n,m,k,c1,c2,ans,a[1010],b[1010];
int dpt[M];
void Add(int x,int y,int z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
bool BFS()
{
int i;
static int q[M],r,h;
memset(dpt,-1,sizeof dpt);
r=h=0;dpt[S]=1;q[++r]=S;
while(r!=h)
{
int x=q[++h];
for(i=head[x];i;i=table[i].next)
if(table[i].f&&!~dpt[table[i].to])
{
dpt[table[i].to]=dpt[x]+1;
q[++r]=table[i].to;
if(table[i].to==T)
return true;
}
}
return false;
}
int Dinic(int x,int flow)
{
int i,left=flow;
if(x==T) return flow;
for(i=head[x];i&&left;i=table[i].next)
if(table[i].f&&dpt[table[i].to]==dpt[x]+1)
{
int temp=Dinic(table[i].to, min(left,table[i].f) );
if(!temp) dpt[table[i].to]=-1;
left-=temp;
table[i].f-=temp;
table[i^1].f+=temp;
}
return flow-left;
}
int main()
{
int i,j,x;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&a[i]),ans+=a[i];
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
for(i=1;i<=n;i++)
{
int temp=b[i]-a[i];
if(temp>0)
Add(S,i,temp),Add(i,S,0),ans+=temp;
else
Add(i,T,-temp),Add(T,i,0);
}
cin>>m;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&c1,&c2);
ans+=c1;ans+=c2;
Add(n+(i<<1),T,c1);
Add(T,n+(i<<1),0);
Add(S,n+(i<<1|1),c2);
Add(n+(i<<1|1),S,0);
for(j=1;j<=k;j++)
{
scanf("%d",&x);
Add(x,n+(i<<1),INF);
Add(n+(i<<1),x,0);
Add(n+(i<<1|1),x,INF);
Add(x,n+(i<<1|1),0);
}
}
while( BFS() )
ans-=Dinic(S,INF);
cout<<ans<<endl;
}