BZOJ3438 小M的作物 <最小割>

Problem

小M的作物

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

Input

第一行包括一个整数$n$
第二行包括$n$个整数，表示$a_i$
第三行包括$n$个整数，表示$b_i$
第四行包括一个整数$m$
接下来$m$行，第$i$行依次输入：

• 一个整数$k_i$，表示第$i$个作物组合中共有$k_i$种作物
• 两个整数$c_{i,1},c_{i,2}$，表示两种收益分别是多少
• $k_i$个整数，表示该组合中的作物编号

Output

只有一行，包括一个整数，表示最大收益

Sample Input

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

Sample Output

11

Explanation

$A$耕地种$1,2$，$B$耕地种$3$，收益$4+2+3+2=11$

HINT

$1\le k<n\le1000$, $0<m\le1000$，保证所有数据及结果不超过$2\times10^9$

标签：最小割

Solution

文理分科加强版，建模稍有变化。

首先容易想到将每个作物作为结点，对于作物$i$，连接$S\to i$容量$a_i$，连接$i\to T$容量$b_i$。割掉一条边表示不选对应的那片田，就可以以最小割的形式处理只考虑选$A$和选$B$收益，不考虑集团收益的问题。

对于每个组合，由于作物个数很多，不能像文理分科一样把失去的收益拆到$S\to i$和$i\to T$上。这里可以建立辅助结点，即给每个组合建立结点。由于存在两种贡献，需要拆成两个节点$p$和$q$，连接$S\to p$容量$c_1$，$q\to T$容量$c_2$。以$p$为例，$S\to p$需要被割去当且仅当此组合中任意作物选择$A$而非$B$，即此组合中存在作物$t$，$t\to T$并未被割掉。因此需要串联，即从$p$连边到此组合中的所有作物，容量$\infty$（从中间割断是没有意义的）。对应地，$q$的连法相同。

建模：

• 对于每个作物$i\in[1,n]$，连接$S\to i$容量$a_i$，$i\to T$容量$b_i$
• 对于每个组合$i$，建立结点$p_i,q_i$，连接$S\to p_i$容量$c_1$，$q_i\to T$容量$c_2$
• 对于每个组合$i$，设其内作物为$x_1\sim x_k$，那么对每个作物$x_j$，连接$p_i\to x_j$容量$\infty$，$x_j\to q_i$容量$\infty$

Code

#include <bits/stdc++.h>
#define MAX_N 4000
#define MAX_M 5000000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, sum, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];
void init() {s = 0, t = 4000, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0; cpy(); while (BFS()) ret += DFS(s, INF), rec(); return ret;}
int main() {
    read(n), init();
    for (int i = 1, x; i <= n; i++) read(x), addedge(s, i, x), sum += x;
    for (int i = 1, x; i <= n; i++) read(x), addedge(i, t, x), sum += x;
    read(m);
    for (int i = 1, c1, c2, k; i <= m; i++) {
        read(k), read(c1), read(c2), sum += c1+c2;
        addedge(s, n+i*2-1, c1), addedge(n+i*2, t, c2);
        for (int j = 0, x; j < k; j++)
            read(x), addedge(n+i*2-1, x, INF), addedge(x, n+i*2, INF);
    }
    return printf("%d\n", sum-Dinic()), 0;
}