inic声明:本博客默认读者会最大流最小割的定理，会Dinic,
最小割在数值上 == 最大流
<mark>但是在意义上没有任何关系，姑且可以这样求得最小割，当然可以自行百度最小割的证明定理</mark>
还是从题目开始说起
洛谷P1361

<mark>题目描述</mark>

小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1…n编号）。
现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则***有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益。
小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？

<mark>输入格式</mark>

第一行包括一个整数n
第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，
对于接下来的第i行：第一个整数ki，表示第i个作物组合***有ki种作物，
接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。

<mark>输出格式</mark>

只有一行，包括一个整数，表示最大收益

<mark>输入输出样例</mark>
**输入 **
3
4 2 1
2 3 2
1
2 3 2 1 2
**输出 **
11

如果说我们不考虑额外的收益那么我们很容易建立如下的模型

这样建图后我们在跑一遍最大流求得最小割就好了，有些人不清楚为什么要求最小割这里简单的解释一下，我们建立原点和汇点分别表示两块地但是如果即链接了A又连接了B那肯定是不行的，因为一种作物只可以种植在唯一的土地上，那么也就是说我们必须要断开一条边，既然要取得最大的收益那么我们肯定要断掉最小的边，咦~~~~~~~~~这不是最小割嘛233333；
但是现在有一种额外收益的情况，那我们就要建立关于额外收益的点，也就是辅助点或者说是虚点
<mark>那么我们建立如下模型</mark>

我们建立两个虚点，v1和v2分别表示一个集合对A或者B作出贡献的收益点，这样我们跑一遍最大流求出最小割，就OKK了 啊
AC代码

/* *　　　　　　　 ┏┓ ┏┓+ + *　　　　　　　┏┛┻━━━━━━━┛┻┓ + + *　　　　　　　┃　　　　　　 ┃ *　　　　　　　┃　　　━　　　┃ ++ + + + *　　　　 　 █████━█████ ┃+ *　　　　　　　┃　　　　　　 ┃ + *　　　　　　　┃　　　┻　　　┃ *　　　　　　　┃　　　　　　 ┃ + + *　　　　　　　┗━━┓　　　 ┏━┛ * ┃　　 ┃ *　　　　　　　　　┃　　 ┃ + + + + *　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting *　　　　　　　　　┃　　　┃ + 　　　　 神兽保佑,代码无bug *　　　　　　　　　┃　　　┃ *　　　　　　　　　┃　　　┃　　+ *　　　　　　　　　┃　 　 ┗━━━┓ + + *　　　　　　　　　┃ 　　　　　┣┓ *　　　　　　　　　┃ 　　　　　┏┛ *　　　　　　　　　┗┓┓┏━━━┳┓┏┛ + + + + *　　　　　　　　　 ┃┫┫　 ┃┫┫ *　　　　　　　　　 ┗┻┛　 ┗┻┛+ + + + */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
#include<cmath>
#include<functional>
#include<stack>

using namespace std;

const int maxn = 255;
const int MAXN = 4e6 + 5;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int to, w, next;
}edg[MAXN];

int head[MAXN], dep[MAXN], cnt = 0;

void init()
{
	memset(head, -1, sizeof(head));
	cnt = 0;
}

void Add_edge(int u, int v, int w)
{
	edg[cnt].w = w;
	edg[cnt].to = v;
	edg[cnt].next = head[u];
	head[u] = cnt++;
	edg[cnt].w = 0;
	edg[cnt].to = u;
	edg[cnt].next = head[v];
	head[v] = cnt++;
}

bool Bfs(int s, int t)
{
	memset(dep, 0, sizeof(dep));
	queue<int> q;
	while(!q.empty()) q.pop();
	dep[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int p = q.front();
		q.pop();
		for(int i = head[p]; i != -1; i = edg[i].next)
		{
			int w = edg[i].w; int v = edg[i].to;
			if(w && !dep[v])
			{
				dep[v] = dep[p] + 1;
				q.push(v);
				if(v == t)
					return true;
			}
		}
	}
	if(dep[t])
        return true;
    else
	return false;
}

int DFS(int s, int mw, int t)
{
	if(s == t)
		return mw;
	int res = mw;
	for(int i = head[s]; i != -1; i = edg[i].next)
	{
	    if(!res) return mw;
		int v = edg[i].to;
		if(edg[i].w && dep[v] == dep[s] + 1)
		{
			int k = DFS(v, min(res, edg[i].w), t);
			if(!k) dep[v] = 0;
			edg[i].w -= k;
			edg[i^1].w += k;
			res -= k;
		}
	}
	return mw - res;
}

int Dinic(int s, int t)
{
	int tot = 0;
	while(Bfs(s, t))
	{
		while(int d = DFS(s, INF, t))
			tot += d;
	}
	return tot;
}

//最小割在数值上等于最大流
//辅助点建图法

int main()
{
	int n, w, m, k, c1, c2, u;
	long long sum = 0;
	scanf("%d", &n);
	init();
	int s = n + 1, t = n + 2;
	register int i;
	for(i = 1; i <= n; ++i)
	{
		scanf("%d", &w);
		sum += w;
		Add_edge(s, i, w);
	}
	for(i = 1; i <= n; ++i)
	{
		scanf("%d", &w);
		sum += w;
		Add_edge(i, t, w);
	}
	scanf("%d", &m);
	for(int a = 1; a <= m; ++a)
	{
		scanf("%d %d %d", &k, &c1, &c2);
		int v1 = n + 2 + a;
		int v2 = n + 2 + a + m;
		sum += (c1 + c2);
		Add_edge(s, v1, c1);
		Add_edge(v2, t, c2);
		for(int j = 1; j <= k; ++j)
		{
			scanf("%d", &u);
			Add_edge(v1, u, INF);
			Add_edge(u, v2, INF);
		}
	}
	cout << sum - Dinic(s, t);
}

有一个 坑点就是数据范围要开到4e6才能过，，，，切记初始化