最近房地产商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求出一个收益最大的方案么?
【bzoj2132】【圈地计划】【最小割】
发布日期:2021-11-16 15:38:22
浏览次数:6
分类:技术文章
本文共 1345 字,大约阅读时间需要 4 分钟。
Description
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
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
【数据规模】
对于100%的数据有N,M≤100
题解:
首先对图黑白染色.
如果i是黑点,从源点向i连权值a[i]的边,从i向汇点连权值b[i]的边。
如果i是白点,从源点向i连权值b[i]的边,从i向汇点连权值a[i]的边。
相邻点i,j之间连权值c[i]+c[j]的边。
最小割即为损失的最小价值。用总价值减一下即可。
代码:
#include#include #include #define N 110#define M 1000010#define INF 0x7fffffffusing namespace std;int cnt(1),point[N*N+2],next[M],st(1),T,cur[N*N+2],dis[N*N+2],gap[N*N+2];int a[N][N],b[N][N],c[N][N],n,m,pre[N*N+2],sum,x[4]={1,0,-1,0},y[4]={0,1,0,-1};bool f; struct use{int st,en,v;}e[M];void add(int x,int y,int v){ // cout< <<' '< <<' '< < n||yy<1||yy>m) continue; add(cal(i,j),cal(xx,yy),c[i][j]+c[xx][yy]);sum+=c[i][j]; } } printf("%d\n",sum-isap());}
转载地址:https://blog.csdn.net/sunshinezff/article/details/50992237 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月07日 06时06分25秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Javascript到PHP加密通讯的简单实现
2019-04-27
德国SNS交友/视频网站Poppen.de的技术架构分享
2019-04-27
UNIX环境编程
2019-04-27
一笔画问题【数据结构-图论】
2019-04-27
红黑树
2019-04-27
安装多个gcc
2019-04-27
Linux0.01内核根目录Makefile注释
2019-04-27
【CSDN2012年度博客之星】需要您的一票,感谢大家的支持
2019-04-27
PHP对于浮点型的数据需要用不同的方法去解决
2019-04-27
Tokyo Cabinet 安装
2019-04-27
Flink在美团的应用与实践听课笔记
2019-04-27
Java多线程的11种创建方式以及纠正网上流传很久的一个谬误
2019-04-27
JDK源码研究Jstack,JMap,threaddump,dumpheap的原理
2019-04-27
Java使用字节码和汇编语言同步分析volatile,synchronized的底层实现
2019-04-27
javac编译原理和javac命令行的使用
2019-04-27
Unity使用UnityWebRequest实现本地日志上传到web服务器
2019-04-27
Unity使用RenderTexture实现裁切3D模型
2019-04-27
美术和程序吵架,原来是资源序列化格式设置不统一
2019-04-27
Unity iOS接SDK,定制UnityAppController
2019-04-27
Unity iOS接SDK前先要了解的知识(Objective-C)
2019-04-27