BZOJ3438 小M的作物

我以为是最大权闭合子图来着。然后好像就直接最小割就行了吧。突然觉得我的网络流好弱。

建源汇，分别连每个作物。对于每个组合建两个点分别边源汇，然后中间像源汇一样连它的成员。如果全在一边，那么会有一条边不用割。这也是一个集合都选对答案有贡献的建图方式。

然后就完了。建图和dinic都写得有些丑，所以调了半天。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct edge {
	int t, c;
	edge *next, *rv;
};

const int maxn = 3009;
const int inf = 0x3f3f3f3f;

int n, m, c, d[maxn], t, st, te;
edge *head[maxn];

inline edge* newEdge(int u, int v, int c) {
	edge* e(new edge);
	e-> t = v;
	e-> c = c;
	e-> next = head[u];
	return head[u] = e;
}
inline void addEdge(int u, int v, int c) {
	edge *a(newEdge(u, v, c)), *b(newEdge(v, u, 0));
	a-> rv = b;
	b-> rv = a;
}

bool bfsBuild() {
	static int q[maxn];
	int hd(0), tl(1);
	memset(d, 0, sizeof(d));
	d[q[0] = st] = 1;
	while (hd < tl && !d[te]) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next)
			if (e-> c && !d[e-> t]) {
				d[e-> t] = d[p] + 1;
				q[tl ++] = e-> t;
			}
	}
	return d[te];
}
int dfsFind(int p, int c) {
	if (p == te)
		return c;
	int s(0);
	edge *e;
	for (e = head[p]; e && c; e = e-> next)
		if (e-> c && d[e-> t] == d[p] + 1) {
			int x(dfsFind(e-> t, min(c, e-> c)));
			s += x;
			c -= x;
			e-> c -= x;
			e-> rv-> c += x;
		}
	if (!e)
		d[p] = 0;
	return s;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	c = 0;
	scanf("%d", &n);
	st = n;
	te = n + 1;
	c = n + 2;
	t = 0;
	memset(head, 0, sizeof(head));
	for (int i = 0; i < n; ++ i) {
		int a;
		scanf("%d", &a);
		t += a;
		addEdge(st, i, a);
	}
	for (int i = 0; i < n; ++ i) {
		int a;
		scanf("%d", &a);
		t += a;
		addEdge(i, te, a);
	}
	scanf("%d", &m);
	for (int i = 0; i < m; ++ i) {
		int k, c1, c2, u, v;
		scanf("%d%d%d", &k, &c1, &c2);
		t += c1 + c2;
		u = c ++;
		v = c ++;
		addEdge(st, u, c1);
		addEdge(v, te, c2);
		for (int i = 0; i < k; ++ i) {
			int x;
			scanf("%d", &x);
			-- x;
			addEdge(u, x, inf);
			addEdge(x, v, inf);
		}
	}
	while (bfsBuild())
		t -= dfsFind(st, inf);
	printf("%d\n", t);
}