https://codeforces.com/contest/311/problem/E
题意概述
给定 \(n\) 只狗，初始性别为 \(0\) 或 \(1\)，可以花费 \(v_i\) 元改变第 \(i\) 只狗的性别。
有 \(m\) 个富人，第 \(i\) 个富人会指定 \(k_i\) 只特定的狗和一个性别，如果指定的所有狗的性别与指定的性别一致，获得 \(w_i\) 元；如果该富人是你的朋友，且你没有满足他的要求，需要支付给他固定 \(g\) 元。
求最大净收益（可能为负）。
思路
为了满足某些要求以获得利润，可能需要花费代价，存在依赖关系且要求最大化利润，符合最大权闭合子图模型。
最大权闭合子图
最大权闭合子图：在一个有向图中，每个点有点权，选择权值和最大的一个子图，并且满足子图中每个点的所有后继都在子图中，这个子图就是最大权闭合子图。
求解最大权的方法：虚拟出源点 \(s\) 和汇点 \(t\)，从 \(s\) 向原图中所有点权为正的点连边，容量为点权；从原图中所有点权为负的点向 \(t\) 连边，容量为点权的绝对值；对于原图中的边，容量为无穷大。最终答案为原图中的所有正点权之和 \(-\) 最小割。
解释如下：
首先规定分到 \(S\) 集的点作为被选中作为子图中的点。
考虑割的意义：如果割掉 \(s\) 到 \(i\) 的边，那么 \(i\) 不在 \(S\) 集中，相当于不选 \(i\) 作为子图中的点；如果割掉 \(i\) 到 \(t\) 的边，那么 \(i\) 不在 \(T\) 集中，相当于选 \(i\) 作为子图中的点。
因此，割的容量为：不选的正点权之和 \(+\) 选择的负点权的绝对值之和。
而子图的权值和为：所有的正点权之和 \(-\) 不选的正点权之和 \(-\) 选择的负点权的绝对值之和，也就是：所有正点权之和 \(-\) 割的容量。
因此只需要最小化割的容量即可。同时由于原图的边容量为无穷大，在最小割中不可能被割掉，选中的子图满足原图的依赖关系。
回到本题。
为了方便处理，先将所有点的性别都改成 \(1\)，此时的收益为：要求性别为 \(1\) 的 \(w_i\) 之和 \(-\) 初始性别为 \(0\) 的点的 \(v_i\) 之和 \(-\) 要求性别为 \(0\) 且是朋友的要求数量 \(\cdot g\)。
对于每个点，规定选中某点代表改变该点的性别。如果原本性别为 \(0\)，改变性别相当于反悔，贡献为 \(v_i\)；如果原本性别为 \(1\)，贡献为 \(-v_i\)。
对于每个要求，虚拟成新点。
如果要求性别为 \(0\)，选择该要求需要将所有关联点性别都改成 \(0\)，于是从该虚拟点向所有关联点连边。如果不是朋友，贡献为 \(w_i\)；否则为 \(w_i + g\)；
如果要求性别为 \(1\)，选择该要求需要所有关联点中任意一个被修改成 \(0\)，于是从所有关联点向该虚拟点连边。如果不是朋友，贡献为 \(-w_i\)，否则为 \(- w_i - g\)。
将贡献作为点权，求出最大权闭合子图即可。
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll INF = 9e18;class Q{
public:int t,f,k;ll w;vector<int> a;Q() = default; Q(int t,int f,int k,ll w,vector<int>& a):t(t),f(f),k(k),w(w),a(a){}
};void solve(){int n,m,g;cin >> n >> m >> g;vector<int> sex(n+1);vector<ll> V(n+1);for (int i=1;i<=n;i++){cin >> sex[i];}for (int i=1;i<=n;i++){cin >> V[i];}vector<Q> que(m+1);for (int i=1;i<=m;i++){int t,k;ll w;cin >> t >> w >> k;vector<int> a(k+1);for (int j=1;j<=k;j++){cin >> a[j];}int f;cin >> f;que[i] = {t,f,k,w,a};}ll res = 0;for (int i=1;i<=n;i++){if (sex[i]==0){res -= V[i];}}for (int i=1;i<=m;i++){if (que[i].t==1){res += que[i].w;}if (que[i].t==0 && que[i].f==1){res -= g;}}ll sum = 0;vector<vector<array<ll,3>>> adj(n+m+3);int s=n+m+1,t=n+m+2;auto add = [&](int u,int v,ll w){adj[u].push_back({w,(int)adj[v].size(),v});adj[v].push_back({0,(int)adj[u].size()-1,u});};for (int i=1;i<=n;i++){if (sex[i]==0){add(s,i,V[i]);sum += V[i];}else{add(i,t,V[i]); }}for (int i=1;i<=m;i++){if (que[i].t==0){add(s,i+n,que[i].w+(que[i].f?g:0));sum += que[i].w+(que[i].f?g:0);for (int j=1;j<=que[i].k;j++){add(i+n,que[i].a[j],INF);}}else{add(i+n,t,que[i].w+(que[i].f?g:0));for (int j=1;j<=que[i].k;j++){add(que[i].a[j],i+n,INF);}}}vector<int> cur,depth;auto bfs = [&](){depth = vector<int>(n+m+3,-1);queue<int> q;depth[s] = 0;q.push(s);while (!q.empty()){int u = q.front();q.pop();for (auto& [w,rev,v]:adj[u]){if (w>0 && depth[v]==-1){depth[v] = depth[u]+1;q.push(v);if (v==t) return true;}}}return false;};function<ll(int,ll)> dfs = [&](int u,ll mf){if (u==t) return mf;ll curf = 0;int len = adj[u].size();for (int& i=cur[u];i<len;i++){auto& [w,rev,v] = adj[u][i];if (w==0 || depth[v]!=depth[u]+1) continue;ll f = dfs(v,min(mf,w));curf += f;adj[v][rev][0] += f;mf -= f;w -= f;if (mf==0) break;}if (curf==0){depth[u] = -1;}return curf;};ll mxf = 0;while (bfs()){cur = vector<int>(n+m+3);mxf += dfs(s,INF);}cout << res+sum-mxf << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}