Description：

两块耕地， $n$ 种种子，每种可以选择种在 $A$ 或 $B$ 分别可以获得不同价值，有一些特殊的种子集合，如果这个集合中所有种子种在 $A$ 或 $B$ 上可以获得不同的额外价值，最大化总价值。

$1\le n\le 1000$

Solution：

二元关系最小割，对于额外价值把他拆成两个点，一个点与源点连边，容量为在 $A$ 的价值，另一个点与汇点连边，容量为在 $B$ 的价值，这点与二元关系最小割相同，然后第一个点向所有集合中的点连容量 $\infty$ 的边，所有集合中的点向另一个点也这样连代表这些便不能被割断，要么 $S$ 到 $s'$ 被割，要么另一边被割，要么都割，这样求最小割，再用所有权值减就是答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1050

int s,t;

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt,f;

}e[MAXN * 2 * 2 + MAXN * 2 * 2 + MAXN * MAXN * 2 * 2];

int edgenum = 0;

int lin[MAXN * 3];

void add(int a,int b,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int ch[MAXN * 3];

bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return ch[t] != -1;

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	s = n + 1;t = s + 1;

	int k;

	int sum = 0;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&k);

		add(s,i,k);

		sum += k;

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&k);

		add(i,t,k);

		sum += k;

	}

	scanf("%d",&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&k,&a,&b);

		add(s,n + 2 + (i << 1),a);

		add(n + 2 + (i << 1 | 1),t,b);

		sum += a + b;

		for(int j = 1;j <= k;++j)

		{

			scanf("%d",&a);

			add(n + 2 + (i << 1),a,INF);

			add(a,n + 2 + (i << 1 | 1),INF);

		}

	}

	cout << sum - dinic() << endl;

	return 0;

}