[洛谷P1361]小M的作物

题目大意：将作物种在A，B两地，对于每种作物，种A，B分别有不同的收益，对于一些特殊的作物集合，共同种到A，B集合分别有一些额外收益。求最大收益。

题解：最小割，S向i连容量为$a_i$的边，i向T连容量为$b_i$，对于每个集合，建两个大点，把每组内的点与其连接，容量为inf，两个大点分别与原点或汇点相连，容量为$c_{i1}$和$c_{i2}$

卡点：1.把inf的边设成了双向边

C++ Code：

#include <cstdio>

#include <cstring>

#define N 4010

#define M 2003010

using namespace std;

const int inf = 0x3f3f3f3f;

int st, ed , sum;

int d[N], q[N], h, t;

int n, m, k, o, c1, c2;

int cnt = 2, head[N];

struct Edge {

	int to, nxt, w;

}e[M << 1];

inline int min(int a, int b) {return a < b ? a : b;}

void addE(int a, int b, int c){

	e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;

	e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1;

	cnt += 2;

}

void addE_(int a, int b, int c){

	e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;

	e[cnt ^ 1] = (Edge) {a, head[b], c}; head[b] = cnt ^ 1;

	cnt += 2;

}

bool bfs() {

	memset(d, 0, sizeof d);

	d[q[h = t = 0] = st] = 1;

	while (h <= t) {

		int u = q[h++];

		if (u == ed) return true;

		for (int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if ((!d[v]) && (e[i].w)){

				d[v] = d[u] + 1;

				q[++t] = v;

			}

		}

	}

	return d[ed];

}

int dfs(int u, int low) {

	if ((u == ed) || (low <= 0)) return low;

	int res = 0;

	for (int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if ((d[v] == d[u] + 1) && (e[i].w)){

			int w = dfs(v, min(e[i].w, low - res));

			e[i].w -= w;

			e[i ^ 1].w += w;

			res += w;

			if (res == low) return res;

		}

	}

	if (!res) d[u] = -1;

	return res;

}

void dinic() {

	int ans = 0;

	while (bfs()) {

		ans += dfs(st, inf);

//		printf("%d\n", ans);

	}

	printf("%d\n", sum - ans);

}

int main() {

	scanf("%d", &n);

	st = 0; ed = 4009;

	for (int i = 1; i <= n; i++) {scanf("%d", &o); addE(st, i, o); sum += o;}

	for (int i = 1; i <= n; i++) {scanf("%d", &o); addE(i, ed, o); sum += o;}

	scanf("%d", &m);

	for (int l = 1; l <= m; l++) {

		scanf("%d%d%d", &k, &c1, &c2); sum += c1 + c2;

		addE(st, l + n, c1);

		addE(l + n + m, ed, c2);

		for (int i = 1; i <= k; i++) {scanf("%d", &o); addE(l + n, o, inf); addE(o, l + n + m, inf);}

	}

	dinic();

	return 0;

}