Luogu1361 小M的作物

Link

Sol

单独种在A中连一个点, 单独种在B中连一个点,一起种在A或B中分别连点.

没了

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 2e6 + 5;
const int inf = 1e18;

int n, m, s, t, cnt, num = 1;
int head[SIZE], dep[SIZE], cur[SIZE];

struct node {
    int to, v, nxt;
} edge[SIZE << 1];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void addEdge(int u, int v, int d) {
    edge[++ num].to = v, edge[num].v = d, edge[num].nxt = head[u];
    head[u] = num;
}

inline int bfs() {
    std::queue < int > q;
    for (int i = 1; i <= SIZE - 1; ++ i) dep[i] = inf;
    dep[s] = 0, cur[s] = head[s], q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (edge[i].v <= 0 || dep[v] != inf) continue;
            dep[v] = dep[u] + 1, cur[v] = head[v];
            q.push(v);
            if (v == t) return 1;
        }
    }
    return 0;
}

inline int dinic(int u, int flow) {
    if (u == t) return flow;
    int ans = 0, k = 0;
    for (int i = cur[u], v; i && flow; i = edge[i].nxt) {
        v = edge[i].to, cur[u] = i;
        if (edge[i].v > 0 && dep[v] == dep[u] + 1) {
            k = dinic(v, std::min(flow, edge[i].v));
            if (!k) dep[v] = inf;
            edge[i].v -= k, edge[i ^ 1].v += k;
            ans += k, flow -= k;
        }   
    }
    return ans;
}

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(); s = 2e5 + 1, t = 2e5 + 2; int minCut = 0;
    for (int i = 1; i <= n; ++ i) {
        int ai = read(); minCut += ai;
        addEdge(s, i, ai); addEdge(i, s, 0);
    }
    for (int i = 1; i <= n; ++ i) {
        int bi = read(); minCut += bi;
        addEdge(i, t, bi); addEdge(t, i, 0);
    }
    m = read(); cnt = n;
    for (int i = 1; i <= m; ++ i) {
        int ki = read(), c1 = read(), c0 = read();
        int vir1 = ++ cnt, vir2 = ++ cnt; minCut += (c0 + c1);
        addEdge(s, vir1, c1); addEdge(vir1, s, 0);
        addEdge(vir2, t, c0); addEdge(t, vir2, 0);
        for (int j = 1, u; j <= ki; ++ j) {
            u = read();
            addEdge(vir1, u, inf); addEdge(u, vir1, 0);
            addEdge(u, vir2, inf); addEdge(vir2, u, 0);
        }
    }
    int maxFlow = 0;
    while (bfs()) maxFlow += dinic(s, inf);
    printf("%lld\n", minCut - maxFlow);
    return 0;
}