题目地址：洛谷：【P1361】小M的作物 – 洛谷、BZOJ：Problem 3438. — 小M的作物

题目描述

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

题意简述

有两块田A和B，每种作物种在A会得到一些收益，种在B会得到不同的收益。另有条件若干，若每个条件集合中所有作物都种在A获得额外收益，都种在B获得不同的额外收益。求最大收益。

输入输出格式

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

输出格式：
只有一行，包括一个整数，表示最大收益

输入输出样例

输入样例#1：

3
4 2 1
2 3 2
1
2 3 2 1 2

输出样例#1：

11

说明

样例解释
A耕地种1，2，B耕地种3，收益4+2+3+2=11。
数据范围与约定
1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。

题解

一股最小割的画风。首先每个作物选A选B显然是用最小割求，对于额外收益的条件，我们考虑拆成都选A、都选B两个点，分别向A、B对应的源汇点连容量收益的边，再向作物连容量无限的边，这样，如果作物有选A的，那么拆出连向B的点的收益边必须割，依次类推。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 3005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 12];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    std::queue<int> que;
    memset(level, -1, sizeof(level));
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(level[v] == -1 && gra[i].cap) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(level[v] == level[u] + 1 && gra[i].cap) {
            int f = dfs(v, t, std::min(left, gra[i].cap));
            if(f) {
                flow += f; left -= f; gra[i].cap -= f; gra[i ^ 1].cap += f;
                if(!left) return flow;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) flow += f;
    }
    return flow;
}

int n, m, a[MAXN], b[MAXN], sum, t, S, T;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); 
    for(int i = 1; i <= n; i++) {
        a[i] = readint(); sum += a[i];
    }
    for(int i = 1; i <= n; i++) {
        b[i] = readint(); sum += b[i];
    }
    m = readint(); S = n + m * 2 + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        addedge(S, i, a[i]); addedge(i, T, b[i]);
    }
    for(int i = 1, k, c1, c2; i <= m; i++) {
        k = readint(); c1 = readint(); c2 = readint(); sum += c1 + c2;
        addedge(S, n + i, c1); addedge(n + m + i, T, c2);
        while(k--) {
            t = readint();
            addedge(n + i, t, INF); addedge(t, n + m + i, INF);
        }
    }
    sum -= dinic(S, T);
    printf("%d", sum);
    return 0;
}