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;
}
Comments | NOTHING