BZOJ3438 小M的作物

			    <div class="post_brief"><p>
我以为是最大权闭合子图来着。然后好像就直接最小割就行了吧。突然觉得我的网络流好弱。</p>

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

然后就完了。建图和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", &amp;n);
st = n;
te = n + 1;
c = n + 2;
t = 0;
memset(head, 0, sizeof(head));
for (int i = 0; i &lt; n; ++ i) {
	int a;
	scanf("%d", &amp;a);
	t += a;
	addEdge(st, i, a);
}
for (int i = 0; i &lt; n; ++ i) {
	int a;
	scanf("%d", &amp;a);
	t += a;
	addEdge(i, te, a);
}
scanf("%d", &amp;m);
for (int i = 0; i &lt; m; ++ i) {
	int k, c1, c2, u, v;
	scanf("%d%d%d", &amp;k, &amp;c1, &amp;c2);
	t += c1 + c2;
	u = c ++;
	v = c ++;
	addEdge(st, u, c1);
	addEdge(v, te, c2);
	for (int i = 0; i &lt; k; ++ i) {
		int x;
		scanf("%d", &amp;x);
		-- x;
		addEdge(u, x, inf);
		addEdge(x, v, inf);
	}
}
while (bfsBuild())
	t -= dfsFind(st, inf);
printf("%d\n", t);

}

Comments