题目地址：Codeforces：Problem – 311E – Codeforces、洛谷：【CF311E】Biologist – 洛谷

题目描述

SmallR is a biologist. Her latest research finding is how to change the sex of dogs. In other words, she can change female dogs into male dogs and vice versa.
She is going to demonstrate this technique. Now SmallR has n dogs, the costs of each dog’s change may be different. The dogs are numbered from 1 to n. The cost of change for dog i is vi RMB. By the way, this technique needs a kind of medicine which can be valid for only one day. So the experiment should be taken in one day and each dog can be changed at most once.
This experiment has aroused extensive attention from all sectors of society. There are m rich folks which are suspicious of this experiment. They all want to bet with SmallR forcibly. If SmallR succeeds, the i-th rich folk will pay SmallR wi RMB. But it’s strange that they have a special method to determine whether SmallR succeeds. For i-th rich folk, in advance, he will appoint certain ki dogs and certain one gender. He will think SmallR succeeds if and only if on some day the ki appointed dogs are all of the appointed gender. Otherwise, he will think SmallR fails.
If SmallR can’t satisfy some folk that isn’t her friend, she need not pay him, but if someone she can’t satisfy is her good friend, she must pay g RMB to him as apologies for her fail.
Then, SmallR hope to acquire money as much as possible by this experiment. Please figure out the maximum money SmallR can acquire. By the way, it is possible that she can’t obtain any money, even will lose money. Then, please give out the minimum money she should lose.
有N只狗，性别给定，改变性别花费vi。有M个人，想要让某些狗变成某个性别，如果能满足他们的要求则获得收益wi，否则当这个人是你的朋友的时候则要倒贴g，不是朋友的时候没有倒贴。求最大收益。

输入输出格式

输入格式：
The first line contains three integers n, m, g (1 ≤ n ≤ 10^4, 0 ≤ m ≤ 2000, 0 ≤ g ≤ 10^4). The second line contains n integers, each is 0 or 1, the sex of each dog, 0 represent the female and 1 represent the male. The third line contains n integers v1, v2, …, vn (0 ≤ vi ≤ 10^4).
Each of the next m lines describes a rich folk. On the i-th line the first number is the appointed sex of i-th folk (0 or 1), the next two integers are wi and ki (0 ≤ wi ≤ 10^4, 1 ≤ ki ≤ 10), next ki distinct integers are the indexes of appointed dogs (each index is between 1 and n). The last number of this line represents whether i-th folk is SmallR’s good friend (0 — no or 1 — yes).

输出格式：
Print a single integer, the maximum money SmallR can gain. Note that the integer is negative if SmallR will lose money.

输入输出样例

输入样例#1：

5 5 9
0 1 1 1 0
1 8 6 2 3
0 7 3 3 2 1 1
1 8 1 5 1
1 0 3 2 1 4 1
0 8 3 4 2 1 0
1 7 2 4 1 1

输出样例#1：

2

输入样例#2：

5 5 8
1 0 1 1 1
6 5 4 2 8
0 6 3 2 3 4 0
0 8 3 3 2 4 0
0 0 3 3 4 1 1
0 10 3 4 3 1 1
0 4 3 3 4 1 1

输出样例#2：

16

题解

我们考虑利用最小割和最大权闭合子图的模型来解决这个问题。
首先对于狗，我们将边的功能定义为割边=变性。因此对于性别0的狗与源连边，性别1的狗与汇连边，容量为变性开销。这是对狗的一次分类。
接下来我们考虑如何处理条件限制。如果用割边来表示不满足一个条件限制，这个是很好做的。关键在于与狗的联系。我们尝试利用类似的方法把条件分类，要求性别为0的条件与源连边，性别1的条件与汇连边，容量为这个条件的收益。对于条件与狗，我们连容量无限的边，表示一种要求，注意有向边的方向，一定要让流可以向不满足条件的狗的方向流，例如性别为0的条件应该向狗连边，而要求性别为1的则要从狗向条件连边。然后我们会发现，与要求条件相同的狗本来就在条件一侧的子图中，这条边永远不会有流流过，而不同的狗则可能有流流过。
我们来思考一条增广路，一定是源→要求0的条件→性别1的狗→汇，割边时要么选择不满足条件，要么选择给狗变性。另外一种情况同理。因此这种建图方式能够满足我们的要求。
此外，还有倒贴的问题。我们可以对条件与源汇连的边加上这个倒贴的g，当用\sum w_i减掉最小割的时候，不能被满足的条件的g也会同时减去。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#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();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 5];
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) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    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 > 0) {
                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 <= 0) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(left <= 0) 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, g, col[MAXN], vi, coli, wi, ki, dogi, fri, ans, S, T;

// 1 ~ n dog
// n+1 ~ n+m rich folk

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); g = readint();
    S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        col[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        vi = readint();
        if(col[i] == 0) addedge(S, i, vi);
        else addedge(i, T, vi);
    }
    for(int i = 1; i <= m; i++) {
        coli = readint(); wi = readint(); ki = readint();
        ans += wi;
        while(ki--) {
            dogi = readint();
            if(coli == 0) addedge(i + n, dogi, INF);
            else addedge(dogi, i + n, INF);
        }
        fri = readint();
        if(coli == 0) addedge(S, i + n, wi + (fri ? g : 0));
        else addedge(i + n, T, wi + (fri ? g : 0));
    }
    ans -= dinic(S, T);
    printf("%d", ans);
    return 0;
}