#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+5,inf=1e9;
struct Edge{int to,r;ll c;};
vector<Edge>G[N];
int d[N],st,ed,n,m;
ll sum;
inline int id(int p,int x){
    if(p==1) return x;
    if(p==2) return m+x;
    return m+n+x;
}
inline bool bfs(){
	memset(d,-1,sizeof d);
	queue<int>q;q.push(st);d[st]=0;
	while(q.size()){
		int u=q.front();q.pop();
		for(const Edge&e:G[u])
			if(e.c&&d[e.to]==-1){
				d[e.to]=d[u]+1;q.push(e.to);
				if(e.to==ed)return true;
			}
	}
	return false;
}
inline ll dfs(int u,ll mf){
	if(u==ed)return mf;
	ll t=0;
	for(Edge&e:G[u])
		if(e.c&&d[e.to]==d[u]+1){
			ll f=dfs(e.to,min(mf-t,e.c));
			e.c-=f;G[e.to][e.r].c+=f;t+=f;
			if(t==mf)break;
		}
	if(!t)d[u]=-1;
	return t;
}
inline ll dinic(){
	ll mf=0;
	while(bfs())mf+=dfs(st,1e18);
	return mf;
}
void add(int u,int v,ll c){
	G[u].push_back({v,(int)G[v].size(),c});
	G[v].push_back({u,(int)G[u].size()-1,0});
}
int main(){
	scanf("%d",&n);
	sum=0;
	int a[N],b[N];
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
	for(int i=1;i<=n;i++) scanf("%d",&b[i]),sum+=b[i];
	scanf("%d",&m);
	st=0;ed=m+n+m+1;
	for(int i=1;i<=n;i++){
		add(st,id(2,i),a[i]);
		add(id(2,i),ed,b[i]);
	}
	for(int i=1;i<=m;i++){
		int k,c1,c2;
		scanf("%d%d%d",&k,&c1,&c2);
		while(k--){
			int x;
			scanf("%d",&x);
			add(id(1,i),id(2,x),inf);
			add(id(2,x),id(3,i),inf);
		}
		add(st,id(1,i),c1);
		add(id(3,i),ed,c2);
		sum+=c1+c2;
	}
	printf("%lld\n",sum-dinic());
	return 0;
}

$$\Large\texttt{My Blog}$$

题目链接：Luogu 1361

小 M 在开辟了两块巨大的耕地 $A$ 和 $B$（你可以认为容量无穷），现在他有 $n$ 种作物的种子各 $1$ 个，编号为 $1$ 到 $n$。第 $i$ 种作物在 $A$ 中种植可以获得 $a_i$ 的收益，在 $B$ 中种植可以获得 $b_i$ 的收益。某些作物种在同一块耕地中可以获得额外的收益，小 M 找到 $m$ 种作物的组合，每个组合用 $c_1,c_2,k$ 和一个序列 $p_1,p_2,\cdots.p_k$ 表示，代表这 $k$ 种作物共同种在 $A$ 和 $B$ 耕地中可以分别获得 $c_1$ 和 $c_2$ 的额外收益。求收益的最大值。

数据范围：$1\le n,m\le 1000$

Solution

通过「算法笔记」网络流 - 最小割 中问题模型的分析，我们可以发现这题每种作物只能选择一个耕地，满足二者选其一的性质，所以我们可以考虑用最小割来解决。

对于单独的作物直接从源点 $s$ 连边或向 $t$ 连边即可，难点在如何处理组合的关系。

首先明确一点，一个组合就是一个点集，它的贡献有三种情况：对集合 $A$ 有贡献；对集合 $B$ 有贡献；没有任何贡献。这意味着只划分出一种状态是无法描述的，我们需要把 $A$ 和 $B$ 集合分开考虑。

接下来讨论点集 $\{u,v,w\}$ 对集合 $A$ 的贡献。

按照题意，我们的要求是：只要 $u,v,w$ 其中一者被割进了集合 $B$（连向 $t$），那么这个点集都没有贡献。换言之，只要其中一个点在集合 $B$，那么代表点集和集合 $A$ 的连边必须断开！

我们先用一个虚点 $x$ 从 $s$ 连一条代表贡献的边（显然点集必须用一个虚点代替）。如果其中一个点被割进了集合 $B$，那么这条代表贡献的边就要被断开，而 $x$ 到 $u,v,w$ 的边不能被断开。所以我们可以得到：边 $(s,x)$ 的容量为 $c_1$，边 $(x,u),(x,v),(x,w)$ 的容量均为 $\texttt{INF}$（因为只有容量为正无穷的边不可能被断开）。

这个点集对集合 $B$ 的贡献同理。经过检验，我们发现这样的连边方式是完全正确的！直接建图跑最小割即可。

注意：答案为总的收益减去最小割！

时间复杂度：$O(n^2m)$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=3e3+5,M=5e6+5;
int n,m,tot=1,a[N],b[N],lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int p,int x) {
    switch(p) {
        case 1: return x;
        case 2: return m+x;
        case 3: return m+n+x;
    }
}
void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
        cnr[u]=i;
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ans));
            if(x) val[i]-=x,val[i^1]+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;
    return ans;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int x;
        while((x=dfs(s,t,1<<30))) ans+=x;
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),ans+=a[i];
    for(int i=1;i<=n;++i) scanf("%d",&b[i]),ans+=b[i];
    scanf("%d",&m);
    int S=0,T=m+n+m+1;
    for(int i=1;i<=n;++i) addedge(S,id(2,i),a[i]),addedge(id(2,i),T,b[i]);
    for(int i=1;i<=m;++i) {
        int k,c1,c2;
        for(scanf("%d%d%d",&k,&c1,&c2);k--;) {
            int x;
            scanf("%d",&x);
            addedge(id(1,i),id(2,x),1<<30);
            addedge(id(2,x),id(3,i),1<<30);
        }
        addedge(S,id(1,i),c1);
        addedge(id(3,i),T,c2);
        ans+=c1+c2;
    }
    printf("%d\n",ans-dinic(S,T));
    return 0;
}