题目描述
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子
有1个（就是可以种一棵作物）（用1...n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植
可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益
，小M找到了规则中共有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以
获得c2i的额外收益，所以，小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？
输入
第一行包括一个整数n
第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，
对于接下来的第i行：第一个整数ki，表示第i个作物组合中共有ki种作物，
接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。输出格式
输出
只有一行，包括一个整数，表示最大收益
样例输入
3
4 2 1
2 3 2
1
2 3 2 1 2
4 2 1
2 3 2
1
2 3 2 1 2
样例输出
11
样例解释A耕地种1，2，B耕地种3，收益4+2+3+2=11。
1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。
样例解释A耕地种1，2，B耕地种3，收益4+2+3+2=11。
1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。
源汇点分别表示选择种在$A$还是$B$上。将源点与每种作物连边，流量为选$A$的收益；每种作物与汇点连边，流量为$B$的收益。对于每种组合收益可以将它看成两种：一种是选$A$的组合，一种是选$B$的组合。如果是选$A$的组合，新建一个点，将源点连向新建点，流量为对应收益；再将新建点连向组合中所有点，流量为$INF$。如果是选$B$的组合，新建点连向汇点，流量为对应收益；再将组合中所有点连向新建点，流量为$INF$。答案就是总收益$-$最小割。由于边数较多，需要$dinic$加上多种优化。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int head[4000];
int to[4000000];
int next[4000000];
int val[4000000];
int d[4000];
int q[4000];
int back[4000];
int S,T;
int x,y,k;
int n,m;
int tot=1;
int ans;
void add(int x,int y,int v)
{
tot++;
next[tot]=back[x];
back[x]=tot;
to[tot]=y;
val[tot]=v;
tot++;
next[tot]=back[y];
back[y]=tot;
to[tot]=x;
val[tot]=0;
}
bool bfs(int S,int T)
{
int r=0;
int l=0;
memset(d,-1,sizeof(d));
q[r++]=T;
d[T]=2;
while(l<r)
{
int now=q[l];
for(int i=back[now];i;i=next[i])
{
if(d[to[i]]==-1&&val[i^1]!=0)
{
d[to[i]]=d[now]+1;
q[r++]=to[i];
}
}
l++;
}
if(d[S]==-1)
{
return false;
}
else
{
return true;
}
}
int dfs(int x,int flow)
{
if(x==T)
{
return flow;
}
int now_flow;
int used=0;
for(int &i=head[x];i;i=next[i])
{
if(d[to[i]]==d[x]-1&&val[i]!=0)
{
now_flow=dfs(to[i],min(flow-used,val[i]));
val[i]-=now_flow;
val[i^1]+=now_flow;
used+=now_flow;
if(now_flow==flow)
{
return flow;
}
}
}
if(used==0)
{
d[x]=-1;
}
return used;
}
int dinic()
{
int res=0;
while(bfs(S,T))
{
memcpy(head,back,sizeof(back));
res+=dfs(S,0x3f3f3f3f);
}
return res;
}
int main()
{
scanf("%d",&n);
S=n+1;
T=n+2;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
add(S,i,x);
ans+=x;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
add(i,T,x);
ans+=x;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&x,&y);
add(S,n+2+i,x);
ans+=x;
add(n+2+i+m,T,y);
ans+=y;
for(int j=1;j<=k;j++)
{
scanf("%d",&x);
add(n+2+i,x,INF);
add(x,n+2+i+m,INF);
}
}
printf("%d",ans-dinic());
}