注意一下
以下的最小割指的是删掉一些边，使起点无法到达终点，最小化边权和
所以建单向边
首先每个作物只能在两片田中选一个
考虑2-SAT最小割
作物，A，B田均化为点
首先考虑没有奇怪的相互作用，并用最小割做
显然每个点从A点连来一条边，向B点连去一条边
相互作用:
肯定不能直接在点上连来连去
分成都种在A，都种在B来考虑
都种在A田:
建个虚点，向集合里的每个点连一条inf边，就割不掉了
考虑什么时候不用割:集合里所有点都从A可达
于是在从A向虚点连一条边，费用为$c1_i$
都种在B田同理
于是dinic即可
复杂度O(玄学)(逃)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
const int inf = 2000000000;
struct edge {
int v, f, nxt;
} e[8000010];
int head[4010], tot = 1, cnt;
int cur[4010], dis[4010];
int n, m, k;
inline void addedge(int u, int v, int f) {
e[++tot] = edge{v, f, head[u]};
head[u] = tot;
e[++tot] = edge{u, 0, head[v]};
head[v] = tot;
}
int s, t;
inline int bfs() {
memset(dis, 0, sizeof(dis));
dis[s] = 1;
queue<int> q;
q.push(s);
memcpy(cur, head, sizeof(cur));
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = head[now]; i; i = e[i].nxt)
if(e[i].f != 0 && dis[e[i].v] == 0) {
dis[e[i].v] = dis[now] + 1, q.push(e[i].v);
if(e[i].v == t) return 1;
}
}
return 0;
}
inline int dfs(int now, int limit) {
if(now == t) return limit;
int ans = 0;
for(int &i = cur[now]; i; i = e[i].nxt) {
if(e[i].f == 0 || dis[e[i].v] != dis[now] + 1) continue;
int lala = dfs(e[i].v, min(limit, e[i].f));
if(lala == 0) dis[e[i].v] = 0;
else ans += lala, limit -= lala, e[i].f -= lala, e[i ^ 1].f += lala;
if(limit == 0) return ans;
}
return ans;
}
inline int dinic() {
int ans = 0;
while(bfs()) ans += dfs(s, inf);
return ans;
}
int sum;
int main() {
scanf("%d", &n);
s = 0;
t = cnt = n + 1;
for(int i = 1, x; i <= n; i++) scanf("%d", &x), addedge(s, i, x), sum += x;
for(int i = 1, x; i <= n; i++) scanf("%d", &x), addedge(i, t, x), sum += x;
scanf("%d", &m);
for(int i = 1, x, c1, c2, r1, r2; i <= m; i++) {
scanf("%d%d%d", &k, &c1, &c2);
r1 = ++cnt;
r2 = ++cnt;
sum += c1 + c2;
addedge(s, r1, c1);
addedge(r2, t, c2);
while(k--) scanf("%d", &x), addedge(r1, x, inf), addedge(x, r2, inf);
}
return printf("%d\n", sum - dinic()), 0;
}