题目大意:将作物种在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;
}

  

05-20 13:06