【bzoj3438】 小M的作物

时间：2022-10-02 15:52:16

http://www.lydsy.com/JudgeOnline/problem.php?id=3438 (题目链接)

题意

　　$n$种作物，每种可以种在A田也可以种在B田，两种种植方法有不同的收益。$m$个组合，如果一个组合中的作物种在同一块田地，那么可以获得额外的收益。问最大收益。

Solution

　　最小割。

　　源点向作物连边，容量$a[i]$，作物向汇点连边，容量$b[i]$。

　　$m$组点，每组两个。第一个由源点连向它，再连向组合中的作物；第二个连向汇点，由组合中的作物连过来。

细节

　　mdzz这数组到底要开多大= =

代码

// bzoj3438

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define inf (1ll<<30)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=5010,maxm=1000010;

int head[maxn],a[maxn],b[maxn],n,m,S,T,cnt=1;

LL ans;

struct edge {int to,next,w;}e[maxm<<1];

void link(int u,int v,int w) {

	e[++cnt]=(edge){v,head[u],w};head[u]=cnt;

	e[++cnt]=(edge){u,head[v],0};head[v]=cnt;

}

namespace Dinic {

	int d[maxn];

	bool bfs() {

		for (int i=S;i<=T;i++) d[i]=-1;

		queue<int> q;q.push(S);d[S]=0;

		while (!q.empty()) {

			int x=q.front();q.pop();

			for (int i=head[x];i;i=e[i].next)

				if (e[i].w && d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to);

		}

		return d[T]>0;

	}

	int dfs(int x,int f) {

		if (x==T || f==0) return f;

		int w,used=0;

		for (int i=head[x];i;i=e[i].next) if (d[e[i].to]==d[x]+1 && e[i].w) {

				w=dfs(e[i].to,min(e[i].w,f-used));

				used+=w;e[i].w-=w;e[i^1].w+=w;

				if (used==f) return used;

			}

		if (!used) d[x]=-1;

		return used;

	}

	LL main() {

		LL flow=0;

		while (bfs()) flow+=dfs(S,inf);

		return flow;

	}

}

int main() {

	scanf("%d",&n);

	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);

	S=0,T=n+2*m+1;

	for (int i=1;i<=n;i++) link(S,i,a[i]),link(i,T,b[i]);

	for (int k,x,y,t,i=1;i<=m;i++) {

		scanf("%d%d%d",&k,&x,&y);

		ans+=x+y;

		link(S,i+n,x);link(i+n+m,T,y);

		for (int j=1;j<=k;j++) scanf("%d",&t),link(i+n,t,inf),link(t,i+n+m,inf);

	}

	printf("%lld",ans-Dinic::main());

	return 0;

}

相关文章