#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e3 + 5, M = 5e6 + 5, INF = 1e7;
int n, m, a[N], b[N], t, len, h[N], top = 1, ans, sum;
int dis[N], cur[N];
vector<int> c;
struct edge{
int v, next, w;
}g[M];
void addedge(int u, int v, int w){
g[++top] = {v, h[u], w}, h[u] = top;
}
queue<int> q;
bool bfs(){
for(int i = 0; i <= len; i++){
dis[i] = INF, cur[i] = h[i];
}
q.push(0), dis[0] = 0;
while(q.size()){
int u = q.front();
q.pop();
for(int i = h[u]; i; i = g[i].next){
int v = g[i].v, w = g[i].w;
if(!w || dis[v] != INF) continue;
dis[v] = dis[u] + 1, q.push(v);
}
}
return dis[t] != INF;
}
int dfs(int u, int sum){
if(u == t) return sum;
int res = 0;
for(int i = cur[u]; i && res != sum; i = g[i].next){
int v = g[i].v, w = g[i].w;
cur[u] = h[u];
if(!w || dis[v] != dis[u] + 1) continue;
int cnt = dfs(v, min(sum - res, w));
res += cnt, g[i].w -= cnt, g[i ^ 1].w += cnt;
}
return res;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i], sum += a[i];
addedge(0, i, a[i]), addedge(i, 0, 0);
}
t = len = n + 1;
for(int i = 1; i <= n; i++){
cin >> b[i], sum += b[i];
addedge(i, t, b[i]), addedge(t, i, 0);
}
cin >> m;
for(int i = 1, k, ad, bd; i <= m; i++){
cin >> k >> ad >> bd;
for(int j = 1, v; j <= k; j++){
cin >> v;
c.push_back(v);
}
sum += ad + bd;
++len;
for(int d : c) addedge(len, d, INF), addedge(d, len, 0);
addedge(0, len, ad), addedge(len, 0, 0);
++len;
for(int d : c) addedge(d, len, INF), addedge(len, d, 0);
addedge(len, t, bd), addedge(t, len, 0);
c.clear();
}
while(bfs()){
ans += dfs(0, INF);
}
cout << sum - ans;
return 0;
}
如果调好了,麻烦@一下我,^_^。Thanks you.