小M的作物最大权闭合子图

题目大意

bzoj 3438

两个田\(A,B\)

\(n\le 1000\)种作物的种子

第\(i\)个种子,种\(A\)价值\(a[i]\)，种\(B\)价值\(b[i]\)

再给出\(m\)个子集

第\(i\)个子集，如果子集中的点都种\(A\)增价\(c[i]\),都种\(B\)增价\(d[i]\)

求最大的价值

分析

我们看\(A\)高兴，我们先都种\(A\)，那么我们直接拿到所有\(a,c\)

我们对方案进行修正

把子集看成点，我们把一个子集拆点拆成\(S_1,S_2\)

选\(S_1\)表示不要\(c\)，选\(S_2\)表示要\(d\)

如果选一个种子\(i\)，那么把它种到\(B\),变价\(b[i]-a[i]\),包含它的子集的\(S_1\)都要选

如果要选择\(S_2\)，则该子集中的种子都要选

有了依赖关系和正权负权

跑一个最大权闭合子图即可

solution

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

const int M=3007;

const int N=2100007;

const int INF=1e9+7;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

struct vec{

	int g[M],te;

	struct edge{

		int y,f,nxt;

		edge(int _y=0,int _f=0,int _n=0){y=_y,f=_f,nxt=_n;}

	}e[N];

	vec(){te=1;}

	inline void push(int x,int y,int f){

		e[++te]=edge(y,f,g[x]);g[x]=te;

		e[++te]=edge(x,0,g[y]);g[y]=te;

	}

	inline int& operator () (int x){return g[x];}

	inline edge& operator [] (int x){return e[x];}

}e;

int n,m,res;

int S,T;

int a[M],b[M];

int c[M],d[M];

inline int id1(int x){return n+x;}

inline int id2(int x){return n+m+x;}

int lev[M];

bool bfs(){

	static int q[M];

	int h=0,t=1,x,p,y;

	memset(lev,0,sizeof(lev));

	lev[S]=1; q[1]=S;

	while(h^t){

		x=q[++h];

		for(p=e(x);p;p=e[p].nxt)

		if(e[p].f&&lev[y=e[p].y]==0){

			lev[y]=lev[x]+1;

			if(y==T) return 1;

			q[++t]=y;

		}

	}

	return 0;

}

int dfs(int x,int fl){

	if(x==T) return fl;

	int p,y,res=0,tp;

	for(p=e(x);p;p=e[p].nxt)

	if(e[p].f&&lev[x]+1==lev[y=e[p].y]){

		tp=dfs(y,min(fl,e[p].f));

		if(tp){

			res+=tp;

			fl-=tp;

			e[p].f-=tp;

			e[p^1].f+=tp;

			if(fl==0) return res;

		}

	}

	if(res==0) lev[x]=0;

	return res;

}

int main(){

	int i,j,x,y,z,tp;

	n=rd();

	for(i=1;i<=n;i++) a[i]=rd();

	for(i=1;i<=n;i++) b[i]=rd();

	m=rd();

	for(i=1;i<=m;i++){

		z=rd(),c[i]=rd(),d[i]=rd();

		x=id1(i),y=id2(i);

		for(j=1;j<=z;j++){

			tp=rd();

			e.push(tp,x,INF);

			e.push(y,tp,INF);

		}

	}

	S=0; T=id2(m)+1;

	for(i=1;i<=n;i++){

		res+=a[i];

		tp=b[i]-a[i];

		if(tp>0) e.push(S,i,tp),res+=tp;

		else e.push(i,T,-tp);

	}

	for(i=1;i<=m;i++){

		res+=c[i];

		x=id1(i),y=id2(i);

		e.push(x,T,c[i]);

		e.push(S,y,d[i]),res+=d[i];

	}

	while(bfs()) res-=dfs(S,INF);

	printf("%d\n",res);

	return 0;

}

巴特西

小M的作物最大权闭合子图

题目大意

分析

solution

最新文章

热门文章

巴特西

小M的作物 最大权闭合子图

题目大意

分析

solution

最新文章

热门文章

小M的作物最大权闭合子图