[BZOJ3438]小M的作物 题解
题目地址:洛谷:【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;
}