Description
经过多年的努力, Philipsweng 在生物和计算机领域取得卓越成就。并研究出可以使牛变性的基因重组技术，获得 20XX 年诺贝尔医学或生理学奖。
现在，Philipsweng 有 \(n\) 头牛，牛从 1 到 \(n\) 编号。最开始时，每头牛都有一个性别 \(s_i\) ( 0 表示雌，1 表示雄)，由于牛与牛之间的基因是不同的，所以使第 \(i\) 头牛变性需要 \(v_i\) 元的花费。
即使 Philipsweng 家很有钱，但是，也承担不起多年的研究费用。这时他就需要一些富豪朋友去资助，例如 dengwxn 等等。
Philipsweng 一共有 \(m\) 位朋友，每位朋友可以资助 \(w_i\) 元，当然, 世上没有免费的午餐。他们会提出一些苛刻的条件。他会选定 \(k_i\) 头牛，以及一个性别，如果最终这 \(k_i\) 头牛都为选定的性别，则满足，否则不满足。Philipsweng 还有一些好朋友，例如 Jason 等等，如果 Philipsweng 不能满足好朋友的条件，不仅不能获得 \(w_i\) 的收益，而且要花 \(g\) 元请好朋友喝茶。
Solution
答案=所有赞助费-变性费用-没拿到的赞助费-请喝茶的费用。
所有的赞助费是已知的，要最大化答案，就是要最小化后面那部分。
因此可以想到最小割，建源点 \(S\) 表示雄性，\(T\) 表示雌性。
然后 \(S\) 向所有雄性牛连边，流量是 \(v_i\)。雌性牛向 \(T\) 连边，代价同理。
然后考虑将朋友也放到图中。
如果朋友要求雄性，就 $S\to n+i\to $ 牛。代价分别是 \(w_i(+g)\) 和 \(inf\)（因为要保证这条边绝对不被割掉）。反之亦然。
那么此时割牛边相当于变性，给人边相当于不要某人的赞助费。
然后就可以愉快的跑最大流了。
Code
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
#define inf 107374180
using namespace std;
struct node
{
int to,next,head,flow;
}a[200005];
queue<int> q;
int n,m,g,S,T,tot=1,xxb,gg,k,x,isf,ans,xb[N],v[N],cur[N<<1],dep[N<<1];
int read()
{
int res=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
return res;
}
void add(int x,int y,int z)
{
a[++tot].to=y;
a[tot].flow=z;
a[tot].next=a[x].head;
a[x].head=tot;
}
bool bfs()
{
for (int i=1;i<=n+m+2;++i)
dep[i]=0;
while (!q.empty()) q.pop();
dep[S]=1;q.push(S);
while (!q.empty())
{
int x=q.front();q.pop();
for (int i=a[x].head;i;i=a[i].next)
{
if (a[i].flow>0&&dep[a[i].to]==0)
{
dep[a[i].to]=dep[x]+1;
q.push(a[i].to);
if (a[i].to==T) return true;
}
}
}
return false;
}
int dfs(int x,int ff)
{
if (x==T) return ff;
int fw=0;
for (int &i=cur[x];i;i=a[i].next)
{
if (a[i].flow>0&&dep[a[i].to]==dep[x]+1)
{
int f=dfs(a[i].to,min(a[i].flow,ff));
a[i].flow-=f;
a[i^1].flow+=f;
fw+=f;
ff-=f;
if (ff<=0) break;
}
}
return fw;
}
int dinic()
{
int res=0;
while (bfs())
{
for (int i=1;i<=n+m+2;++i)
cur[i]=a[i].head;
res+=dfs(S,inf);
}
return res;
}
int main()
{
n=read();m=read();g=read();
S=n+m+1;T=n+m+2;
for (int i=1;i<=n;++i)
xb[i]=read();
for (int i=1;i<=n;++i)
v[i]=read();
for (int i=1;i<=n;++i)
{
if (xb[i]==1) add(S,i,v[i]),add(i,S,0);
else add(i,T,v[i]),add(T,i,0);
}
for (int i=1;i<=m;++i)
{
xxb=read();gg=read();
ans+=gg;
k=read();
for (int j=1;j<=k;++j)
{
x=read();
if (xxb==1) add(n+i,x,inf),add(x,n+i,0);
else add(x,n+i,inf),add(n+i,x,0);
}
isf=read();
if (isf==1) gg+=g;
if (xxb==1) add(S,n+i,gg),add(n+i,S,0);
else add(n+i,T,gg),add(T,n+i,0);
}
printf("%d\n",ans-dinic());
return 0;
}