BZOJ 2132 圈地计划

题目大意

给你$n*m$的一个矩形，每一个单元格上都可以选择建设商业区或者工业区，建设就会有相应的收益($a_i,b_i$)。如果相邻的两块地建设的区不同就会获得这两块区域的奖励($c_i+c_j$)（如果与多个单元格相邻就多次累加），求最大收益。

当时觉得很懵逼（似乎被题目吓到了），现在明白咋做了qwq

最基本的方法就是把所有有关联的点连到一个新点上，之后就可以了。但是要建立$4nm$个点，比较复杂，能不能过未知。

首先发现这个图的单元格可以划分到二分图里，所以反转源汇，一部分点$S \to i$连容量$a_i$,$i \to T$连容量$b_i$，一部分点$S \to i$连容量$b_i$,$i \to T$连容量$a_i$.之后连接所有互通的点，边权来回都是$c_i+c_j$即可。这样如果选择出现偏差就注定会把$c_i+c_j$ban掉，而如果选择一致的话就会要求割掉$c_i+c_j$，最终答案就是$\sum{a_i+b_i}+\sum{c_i+c_j}-mincut$

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 110
#define M 20000
#define K 1000000
#define INF (1<<30)
int n,m,depth[M],S=0,T=M-1;
long long a[N][N],b[N][N],c[N][N],ans;
int to[K],nxt[K],val[K],head[M],tot=1;
queue<int>q;
inline void AE(int x,int y,int a,int b)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=a;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=b;
}
bool BFS()
{
	int i,pos;
	while(!q.empty()) q.pop();
	q.push(S);
	memset(depth,-1,sizeof depth),depth[S]=0;
	while(!q.empty())
	{
		pos=q.front();q.pop();
		for(i=head[pos];i;i=nxt[i])
			if(val[i]&&depth[to[i]]==-1)
			{
				depth[to[i]]=depth[pos]+1;
				if(to[i]==T) return true;
				q.push(to[i]);
			}
	}
	return false;
}
int dinic(int pos,int left)
{
	if(pos==T) return left;
	int i,nleft=left,tmp;
	for(i=head[pos];i;i=nxt[i])
		if(val[i]&&depth[to[i]]==depth[pos]+1)
		{
			tmp=dinic(to[i],min(nleft,val[i]));
			if(!tmp) depth[to[i]]=-1;
			nleft-=tmp,val[i]-=tmp,val[i^1]+=tmp;
			if(!nleft) break;
		}
	return left-nleft;
}
int main()
{
	int i,j,tmp=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%lld",&a[i][j]);
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%lld",&b[i][j]);
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%lld",&c[i][j]);
	for(i=1;i<=n;++i) for(j=1;j<=m;++j)
	{
		ans+=a[i][j]+b[i][j],tmp++;
		if((i+j)&1) AE(S,tmp,a[i][j],0),AE(tmp,T,b[i][j],0);
		else AE(S,tmp,b[i][j],0),AE(tmp,T,a[i][j],0);
		if((i+j)&1)
		{
			if(i>1) AE(tmp,tmp-m,c[i][j]+c[i-1][j],c[i][j]+c[i-1][j]),ans+=c[i][j]+c[i-1][j];
			if(i<n) AE(tmp,tmp+m,c[i][j]+c[i+1][j],c[i][j]+c[i+1][j]),ans+=c[i][j]+c[i+1][j];
			if(j>1) AE(tmp,tmp-1,c[i][j]+c[i][j-1],c[i][j]+c[i][j-1]),ans+=c[i][j]+c[i][j-1];
			if(j<m) AE(tmp,tmp+1,c[i][j]+c[i][j+1],c[i][j]+c[i][j+1]),ans+=c[i][j]+c[i][j+1];
		}
	}
	while(BFS()) ans-=dinic(S,INF);
	printf("%lld\n",ans);
	return 0;
}