题解【P1361 小M的作物】

传送门

$\texttt{Description}$

$n$ 种作物，第 $i$ 种作物在 $A$ 区种植可获得 $a_i$ 的效益，在 $B$ 区种植可获得 $b_i$ 的效益。$m$ 种搭配。指定的作物全部种植于 $A$ 区，可获得 $c_{1,i}$ 的效益，全部种植于 $B$ 区，可获得 $c_{2,i}$ 的效益。求最大获益。

$\texttt{Solution}$

重点讲一下建图原理。

首先发现这是一个二选一的模型，考虑最小割。

假设我们所有方案都取，并且每一种作物在两个耕地都种植了，那么可以获得 $\sum (a_i+b_i)+\sum (c_{1,j}+c_{2,j})$ 的效益，但这样是不合法的，所以使用最小割来割去矛盾的边。最大化价值就是最小化割去的边。

先不考虑搭配。光考虑单在 $A$ 区种植或在 $B$ 区种植。

我们建立源点 $s$，和汇点 $t$，令 $s$ 向每一个 $i$ 连一条容量 $a_i$ 的边，同理，$i$ 向 $t$ 连一条容量 $b_i$ 的边。

那么我们求的最小割肯定会在每一个 $i$ 中选择一个 $a_i$ 或 $b_i$。

现在考虑搭配的方案。

我们把每一个搭配标志成一个点，其中第 $i$ 个搭配标记的点为 $i+n$。

我们发现一个搭配要么在 $A$ 种植要么在 $B$ 种植，所以我们可以将一个搭配裂成两个点 $i+n$ 和 $i+n+m$，分别表示种植在 $A$ 和种植在 $B$。

若种植在 $A$，则其可以获得 $c_{1,i}$ 的效益，我们令 $s$ 连向 $i+n$，流量为 $c_{1,i}$，同理，令 $i+n+m$ 连向 $t$，容量为 $c_{2,i}$。

这样的话最小割肯定会割去 $c_{1,i}$ 或 $c_{2,i}$ 中的一个。

我们将 $i+n$ 连向每一个搭配的作物，每一个搭配的作物再连向 $i+n+m$。

注意到选择一个方案必须选择这里面搭配的所有作物，所以每一个作物都是不可分割的。那么我们将流量设为 $\infty$，最小割不会割去容量为 $\infty$ 的边。

做完了，根据最大流 $=$ 最小割，跑一遍最大流后，用总价值减去最大流即可。

贴一下代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9+10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x0?x:-x;}
const int MAXN(3e3+10);
int n,m,a[MAXN],b[MAXN];
struct E{int to,nxt,flow;};
E edge[MAXN*MAXN];
int head[MAXN],tot(1);
inline void add(int u,int v,int f)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	edge[tot].flow=f;
	return;
}
inline void add_edge(int u,int v,int f)
{
	add(u,v,f);
	add(v,u,0);
	return;
}
int dep[MAXN];
queueq;
int s,t;
int ans;
inline bool bfs()
{
	memset(dep,0,sizeof(dep));
	q.push(s);
	dep[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=edge[i].nxt)
		{
			E e=edge[i];
			if(e.flow&&!dep[e.to])
			{
				dep[e.to]=dep[u]+1;
				q.push(e.to);
			}
		}
	}
	return dep[t];
}
inline int dfs(int u,int in)
{
	if(u==t) return in;
//	printf("%d\n",u);
	int out(0);
	for(register int i=head[u];i&∈i=edge[i].nxt)
	{
		E e=edge[i];
		if(e.flow&&dep[e.to]==dep[u]+1)
		{
			int now=dfs(e.to,Min(e.flow,in));
			edge[i].flow-=now;
			edge[i^1].flow+=now;
			in-=now;
			out+=now;
		}
	}
	if(out==0) dep[u]=0;
	return out;
}
int main()
{
	n=read();
	
	for(register int i=1;i<=n;i++) a[i]=read();
	for(register int i=1;i<=n;i++) b[i]=read();
	m=read();
	s=0,t=n+m+m+1;
	for(register int i=1;i<=n;i++)
	{
		add_edge(s,i,a[i]);
		add_edge(i,t,b[i]);
		ans+=a[i]+b[i];
	}
	for(register int i=1;i<=m;i++)
	{
		int k=read();
		int c1=read(),c2=read();
		ans+=c1+c2;
		add_edge(s,n+i,c1);
		add_edge(n+i+m,t,c2);
		while(k--)
		{
			int p=read();
			add_edge(n+i,p,INF);
			add_edge(p,n+i+m,INF);
		}
	}
	while(bfs()) ans-=dfs(s,INF);
	printf("%d\n",ans);
	return 0;
}

　　$$\texttt{The End.by UF}$$