AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3438
这题觉得和上题有点类似吧。
如果没有联合在一起的收成，可以比较好做[我们将属于A的表示到s集中，属于B的表示到t集中]：
s往所有i连a[i]，所有i往t连b[i]。
这样的话，割集表示不选哪些，最后答案就是ans-最小割
现在考虑联合在一起的收成。
我们对于收成(wa,wb)，我们把它拆成两个点u,v，一个与s相连，边权为wa，另一个与t相连，边权为wb。
但是我们需要保证当我选择wa的收益时，需要将令所有关于它的点都不能放在t集合里；当我们选择wb的收益时，需要令所有关于它的点都不在s集合里。
那么怎么构图呢？
就将u往所有相关的i连一条INF的边，所有i往v连一条INF的边。
自从看了那篇有趣的博客，我觉得画图就应该这样画意识流...
这一题RE了很多次，原因就是数组开小了。
边集究竟有多大呢？以最坏的恶意，那么每个收益都是全体点的，那么就是m*n*2条边，然后每个点也要连出去两条，就是(m*n*2+n*2)*2=(2000000+2000)*2=4004000，然后总共的点数是n+2*m=3000个点。
以后要多想一想再来开数组啊....
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; inline int in(){
int x=;char ch=getchar();
while(ch>'' || ch<'') ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x;
} const int maxn=;
const int INF=0x3f3f3f3f; struct Node{
int data,next,low;
}node[]; #define now node[point].data
#define then node[point].next
#define www node[point].low int n,m,cnt,ans;
int s,t,Idex;
int w1[maxn],w2[maxn];
int cur[maxn],head[maxn];
int dis[maxn],que[maxn]; void add(int u,int v,int w){
node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;
node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=;head[v]=cnt++;
} bool BFS(){
memset(dis,-,sizeof(dis));
int H=,T=;que[]=,dis[]=;
while(H<T){
H++;
for(int point=head[que[H]];point!=-;point=then)
if(www && dis[now]<){
dis[now]=dis[que[H]]+;
que[++T]=now;
}
}
return dis[t]>;
} int dfs(int x,int low){
if(x==t) return low;
int Low;
for(int &point=cur[x];point!=-;point=then)
if(www && dis[now]==dis[x]+){
Low=dfs(now,min(low,www));
if(Low){
www-=Low,node[point^].low+=Low;
return Low;
}
}
return ;
} int main(){
#ifndef ONLINE_JUDGE
freopen("3438.in","r",stdin);
freopen("3438.out","w",stdout);
#endif n=in();
for(int i=;i<=n;i++) w1[i]=in(),ans+=w1[i];
for(int i=;i<=n;i++) w2[i]=in(),ans+=w2[i];
m=in();
t=n+(m<<)+;
for(int i=s;i<=t;i++) head[i]=-;
for(int i=;i<=n;i++)
add(s,i,w1[i]),add(i,t,w2[i]);
Idex=n;
int k,wa,wb,x;
for(int i=;i<=m;i++){
k=in(),wa=in(),wb=in();
Idex++;add(s,Idex,wa);ans+=wa;
Idex++;add(Idex,t,wb);ans+=wb;
while(k--){
x=in();
add(Idex-,x,INF),add(x,Idex,INF);
}
}
int flag;
while(BFS()){
for(int i=s;i<=t;i++) cur[i]=head[i];
while(){
flag=dfs(s,INF);
if(!flag) break;
ans-=flag;
}
}
printf("%d",ans);
return ;
}