【BZOJ2132】圈地计划 最小割

【BZOJ2132】圈地计划

Description

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

Input

输入第一行为两个整数,分别为正整数N和M,分别表示区域的行数和列数;第2到N+1列,每行M个整数,表示商业区收益矩阵A;第N+2到2N+1列,每行M个整数,表示工业区收益矩阵B;第2N+2到3N+1行,每行M个整数,表示相邻额外收益矩阵C。第一行,两个整数,分别是n和m(1≤n,m≤100);

任何数字不超过1000”的限制

Output

输出只有一行,包含一个整数,为最大收益值。

Sample Input

3 3
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
1 1 1
1 3 1
1 1 1

Sample Output

81
【数据规模】
对于100%的数据有N,M≤100

题解:如果相邻的两点相同,则获得收益,那么这就变成最小割的裸题了。那么不同怎么办呢?黑白染色,黑点翻转源汇即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define P(A,B) ((A-1)*m+B)
using namespace std;
const int inf=1<<30;
queue<int> q;
int n,m,tot,S,T,ans,cnt=1;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int A[110][110],B[110][110],C[110][110],d[100010],head[100010],next[2000010],val[2000010],to[2000010];
void add(int a,int b,int c)
{
    to[++cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt;
    to[++cnt]=a,val[cnt]=c,next[cnt]=head[b],head[b]=cnt;
}
int dfs(int x,int mf)
{
    if(x==T)    return mf;
    int i,k,temp=mf;
    for(i=head[x];i;i=next[i])
    {
        if(d[to[i]]==d[x]+1&&val[i])
        {
            k=dfs(to[i],min(temp,val[i]));
            if(!k)  d[to[i]]=0;
            val[i]-=k,val[i^1]+=k,temp-=k;
            if(!temp)   break;
        }
    }
    return mf-temp;
}
int bfs()
{
    memset(d,0,sizeof(d));
    while(!q.empty())   q.pop();
    int i,u;
    q.push(S),d[S]=1;
    while(!q.empty())
    {
        u=q.front(),q.pop();
        for(i=head[u];i;i=next[i])
        {
            if(!d[to[i]]&&val[i])
            {
                d[to[i]]=d[u]+1;
                if(to[i]==T)    return 1;
                q.push(to[i]);
            }
        }
    }
    return 0;
}
inline int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}
	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();
	return ret*f;
}
int main()
{
	n=rd(),m=rd(),S=0,T=n*m+1;
	int i,j,k,a,b;
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	A[i][j]=rd(),ans+=A[i][j];
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	B[i][j]=rd(),ans+=B[i][j];
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	C[i][j]=rd();
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)
	{
		a=P(i,j);
		if((i^j)&1)	add(S,a,A[i][j]),add(a,T,B[i][j]);
		else	add(S,a,B[i][j]),add(a,T,A[i][j]);
		for(k=0;k<4;k++)	if(i+dx[k]&&j+dy[k]&&i+dx[k]<=n&&j+dy[k]<=m)
		{
			b=P(i+dx[k],j+dy[k]),ans+=C[i][j];
			add(a,b,C[i][j]);
		}
	}
	while(bfs())	ans-=dfs(S,inf);
	printf("%d",ans);
	return 0;
}
时间: 08-24

【BZOJ2132】圈地计划 最小割的相关文章

BZOJ 2132 圈地计划 最小割

题目大意:给定一个m*n的矩阵,每个位置如果作为商业区或者工业区各有一个收益,如果相邻两块是不同的也会有一个收益,求最大收益 吐槽:住宅区呢- - 地理老师骗我们- - 普通的最小割建图会遇到一个问题: 割断两块之间的边收益为正,即代价为负 因此我们如果正常建最小割,那么两块之间的边权就会是负的 那么我们将这个矩阵黑白染色,将白格ST反向 这样割断两块之间的连边相当于两块选择了同一用途,代价为正 就可以正常跑了 #include <cstdio> #include <cstring>

【BZOJ2132】 圈地计划 最小割

#include <stdio.h> int main() { puts("转载请注明出处谢谢"); puts("http://blog.csdn.net/vmurder/article/details/43201521"); } 题解: 水题,经典模型是两个在一块会损失,显然很好做. 这个同样很好做,就是黑白染色,然后某种颜色该连S集的连T,该连T的连S. 代码: #include <queue> #include <cstdio&g

bzoj2132圈地计划

bzoj2132圈地计划 题意: 一块土地可以纵横划分为N×M块小区域.于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益.而如果区域(i,j)相邻(相邻是指两个格子有公共边)有K块(显然K不超过4)类型不同于(i,j)的区域,则这块区域能增加k×Cij收益.已知收益矩阵A,B,C,求收益最大值. 题解: 因为附加收益不是两两之间的,所以不用考虑除以2的问题.由于需要两块土地属性不同,所以对整个棋盘进行黑白染色.如果一块土地A为黑色,则s->A :c[A商] A->T

线性规划与网络流24题第2题 太空飞行计划 最小割

/** 题目: 线性规划与网络流24题第2题 太空飞行计划 最小割 链接:http://www.cogs.pro/cogs/problem/problem.php?pid=727 题意:lv 思路:最大点权独立集(点集中任意两个点没有边相连,且点权和最大)=点权总和-最小点权覆盖集. 将实验和仪器看做节点. 实验放在二分图的左边, s->x, cap = 实验利润. 仪器放在右边, x->t, cap = 仪器费用. 如果实验u的进行需要仪器v,u->v, cap = INF. ans

BZOJ2132 圈地计划 【最小割】

题目 最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地.据了解, 这块土地是一块矩形的区域,可以纵横划分为N×M块小区域.GDOI要求将这些区域分为商业区和工业区来开发.根 据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值.更具体点,对于第i行第j列的区域, 建造商业区将得到Aij收益,建造工业区将得到Bij收益.另外不同的区域连在一起可以得到额外的收益,即如果区 域(I,j)相邻(

[BZOJ2132] 圈地计划

Time Limit: 2 Sec  Memory Limit: 256 MBSubmit: 1350  Solved: 637[Submit][Status][Discuss] Description 最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地.据了解,这块土地是一块矩形的区域,可以纵横划分为N×M块小区域.GDOI要求将这些区域分为商业区和工业区来开发.根据不同的地形环境,每块小区域建造商业

关于一类最小割图的建法

具体就是bzoj3894文理文科,bzoj2127happiness,bzoj2132圈地计划. 一个图,每个点可以选择A或者B,然后选A是获得收益ai,选b是获得收益bi. 首先是万能方法,对于很多图都可以:一个集合内的点同时选A(或者B)可以获得某个收益ci,那么再建一个点,那个点连A流量为c的边,连集合内每个点一条maxlongint的边,这样就保证如果集合内有选B的,那么这条边一定蛮流(被割掉). bzoj3894就是这种方法,然后多年前写云的小P(还是小M)的牧场也是这种方法. 然后是

【bzoj2132】圈地计划 网络流最小割

题目描述 最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地.据了解,这块土地是一块矩形的区域,可以纵横划分为N×M块小区域.GDOI要求将这些区域分为商业区和工业区来开发.根据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值.更具体点,对于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益.另外不同的区域连在一起可以得到额外的收益,即如果区域(I,j)相邻(相邻

BZOJ 2132 圈地计划(最小割)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2132 题意:n*m的格子染色黑白,对于格子(i,j)染黑色则价值为A[i][j],白色为B[i][j].若一个格子四周不同颜色的有x个,则额外的价值为x*C[i][j].求最大价值. 思路:将格子黑白染色分成两个集合X和Y.S集合为X中的A和Y中的B,T为X中的B和Y中的A.相邻的连边为两个格子的C值之和.总权值减去最小割即是答案. struct node { int v,cap,ne