「bzoj2132」圈地计划 - 最小割+捆绑模型+二分图

题目大意

    最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为$N\times M$块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第$i$行第$j$列的区域，建造商业区将得到$A_{ij}$收益，建造工业区将得到$B_{ij}$收益。另外不同的区域连在一起可以得到额外的收益，即如果区域$(i,j)$相邻（相邻是指两个格子有公共边）有$K$块（显然$K$不超过$4$）类型不同于$(i,j)$的区域，则这块区域能增加$k\times C_{ij}$收益。经过Tiger.S教授的勘察，收益矩阵$A,B,C$都已经知道了。你能帮GDOI求出一个收益最大的方案么？

---

题目分析

因为求最大收益，转化为总和-最小损失（割）。
考虑建立二元组模型。

得到不定方程组（仅考虑额外奖励）：

$$\begin{cases} a+e+d=0 \\ c+e+b=0 \\ a+c=C \\ b+d=C \end{cases}$$

可得：
$e=-C$。
中间的影响边容量为负！即彭天翼所说的$K\lt0$，考虑使用二分图二元组模型：

得到不定方程组（仅考虑额外奖励）：

$$\begin{cases} a+c=0 \\ b+d=0 \\ a+e+d=C \\ c+e+b=C \end{cases}$$

解得一组解：
$a=c=b=d=0,e=C$。

因为原图是网格图，因此满足二分图性质，可以采用以上模型，按照上述解建模即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=10005;
 
struct Edge {
	int from,to,cap,flow;
	Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};
 
struct Dinic {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		memset(vst,0,sizeof(vst));
		memset(dist,0,sizeof(dist));
		queue<int>Q;
		Q.push(t); //反向层次图
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	int dfs(int Now,int a) {
		if(Now==t||a==0)return a;
		int flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		int flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INT_MAX);
		}
		return flow;
	}
} dinic;

const int Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
int n,m,a[105][105],b[105][105],c[105][105],color[105][105],sum=0;

int id(int x,int y) {
	return (x-1)*m+y;
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			a[i][j]=Get_Int(),sum+=a[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			b[i][j]=Get_Int(),sum+=b[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			c[i][j]=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			color[i][j]=((i+j)&1)?1:2;
	int S=n*m+1,T=n*m+2;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(color[i][j]==1) {
				dinic.AddEdge(S,id(i,j),a[i][j]);
				dinic.AddEdge(id(i,j),T,b[i][j]);
			} else {
				dinic.AddEdge(S,id(i,j),b[i][j]);
				dinic.AddEdge(id(i,j),T,a[i][j]);
			}
			for(int k=1; k<=4; k++) {
				int nx=i+Dirx[k],ny=j+Diry[k];
				if(nx<1||ny<1||nx>n||ny>m)continue;
				dinic.AddEdge(id(i,j),id(nx,ny),c[i][j]);
				dinic.AddEdge(id(nx,ny),id(i,j),c[i][j]);
				sum+=c[i][j];
			}
		}
	printf("%d\n",sum-dinic.maxflow(S,T));
	return 0;
}