ZJOI2009狼和羊的故事 代码怎么敲?详细步骤_当前热讯
题目描述
(资料图)
“狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变得非常暴躁,不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地,再就是篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。
输入输出格式
输入格式:
文件的第一行包含两个整数n和m。接下来n行每行m个整数,1表示该格子属于狼的领地,2表示属于羊的领地,0表示该格子不是任何一只动物的领地。
输出格式:
文件中仅包含一个整数ans,代表篱笆的最短长度。
输入样例#1:
2 2 2 2 1 1
输出样例#1:
2
解析:
狼和羊被分开等于说任意狼和羊不连通,容易想到最小割。把狼和羊(1和2)分成两部分,源点向1连边,2向汇点连边,容量inf;1和2交界处连边,然后0向四周连边(因为0周围可任意切割),1向相邻的2连边,容量为1。然后Dinic或者ISAP。
以下是我的代码(依然比较宽。。):
1 #include2 #include3 #include4 #define S (n * m + 1) 5 #define T (n * m + 2) 6 #define ID(x, y) ((x) * m + (y)) 7 #define INF 0x7f7f7f7f 8 using namespace std; 9 10 const int dx[] = {0, 0, 1, -1}; 11 const int dy[] = {-1, 1, 0, 0}; 12 13 struct Edge 14 { 15 int v, next, cap; 16 Edge(int a = 0, int b = 0, int c = 0) 17 :v(a), next(b), cap(c){}; 18 }edge[100020]; 19 int n, m, cnt; 20 int head[10010], cur[10010], dep[10010], map[10010]; 21 22 void AddEdge(int _u, int _v, int _c) 23 { 24 edge[cnt] = Edge(_v, head[_u], _c); 25 head[_u] = cnt++; 26 edge[cnt] = Edge(_u, head[_v], 0); 27 head[_v] = cnt++; 28 } 29 bool bfs() 30 { 31 int queue[10010], qHead = 0, qTail = 0; 32 queue[qTail++] = S; 33 memset(dep, 0, sizeof(dep)); 34 dep[S] = 1; 35 while(qTail > qHead) 36 { 37 int p = queue[qHead++]; 38 for(int i = head[p]; ~i; i = edge[i].next) 39 if(edge[i].cap && !dep[edge[i].v]) 40 { 41 dep[edge[i].v] = dep[p] + 1; 42 queue[qTail++] = edge[i].v; 43 } 44 } 45 return dep[T]; 46 } 47 bool dfs(int now) 48 { 49 if(now == T) return true; 50 for(int &i = cur[now]; ~i; i = edge[i].next) 51 if(edge[i].cap && dep[edge[i].v] == dep[now] + 1 && dfs(edge[i].v)) 52 { 53 edge[i].cap--, edge[i ^ 1].cap++; 54 return true; 55 } 56 return false; 57 } 58 int Dinic() 59 { 60 int res = 0; 61 while(bfs()) 62 { 63 memcpy(cur, head, sizeof(head)); 64 while(dfs(S)) 65 res++; 66 } 67 return res; 68 } 69 int main() 70 { 71 memset(head, -1, sizeof(head)); 72 scanf("%d%d", &n, &m); 73 for(int i = 0; i < n; i++) 74 for(int j = 0; j < m; j++) 75 scanf("%d", &map[ID(i, j)]); 76 for(int i = 0; i < n; i++) 77 for(int j = 0; j < m; j++) 78 switch(map[ID(i, j)]) 79 { 80 case 1: 81 AddEdge(S, ID(i, j), INF); 82 for(int k = 0; k < 4; k++) 83 if(i + dx[k] < n && i + dx[k] >= 0 84 && j + dy[k] < m && j + dy[k] >= 0 85 && map[ID(i + dx[k], j + dy[k])] != 1) 86 AddEdge(ID(i, j), ID(i + dx[k], j + dy[k]), 1); 87 break; 88 case 2: 89 AddEdge(ID(i, j), T, INF); 90 for(int k = 0; k < 4; k++) 91 if(i + dx[k] < n && i + dx[k] >= 0 92 && j + dy[k] < m && j + dy[k] >= 0 93 && map[ID(i + dx[k], j + dy[k])] == 0) 94 AddEdge(ID(i + dx[k], j + dy[k]), ID(i, j), 1); 95 break; 96 default: 97 for(int k = 0; k < 4; k++) 98 if(i + dx[k] < n && i + dx[k] >= 0 99 && j + dy[k] < m && j + dy[k] >= 0100 && map[ID(i + dx[k], j + dy[k])] == 0)101 AddEdge(ID(i, j), ID(i + dx[k], j + dy[k]), 1);102 }103 printf("%d\n", Dinic());104 105 return 0;106 }//Rhein_E
View Code 返回顶部 收缩
转载于:https://www.cnblogs.com/Rhein-E/p/9323589.html
标签:
相关推荐:
最新新闻:
- 云课堂智慧职教网页版登录入口 智慧职教云课堂怎么登录?
- 什么是MSDN?MSDN的结构详情介绍
- DHCP协议简介 DHCP三种分配方式
- 菜鸟教程 - Python 100例 题目解析_环球热门
- Python小白学习之路 执行Python脚本的两种方式
- 全球实时:setTimeout是什么意思?彻底理解setTimeout
- 数据显示:2021年国内应用商店在线App数量减少21.4%
- Java中的BigDecimal类使用 三种类型的构造方法
- 世界时讯:Process类详解 相关类和方法介绍
- 今日热搜:Volatile详解 现代计算机的内存模型的详情介绍
- Scope参数错误或没有Scope权限怎么办?解决办法
- 全球速读:《人人都是产品经理》知识点总结 非功能性需求的分析
- security是什么意思?security详解-即时看
- 观察:什么是Web3(Web3.0)?有什么优点?
- 准确进行网速测试的方法有哪些?适用于电信,联通等多种网络
- 【环球聚看点】蕾哈娜抖音首次晒娃:这表情 确定是亲生的!
- JavaScript简介 弱类型语言详情介绍
- 什么是域?AD域的详细介绍
- ZJOI2009狼和羊的故事 代码怎么敲?详细步骤_当前热讯
- 手游《古惑狼:全速冲锋》将停服 发售不到2年|焦点速递
- 读书郎学生电脑如何下载?读书郎电脑下载步骤
- 京东联盟/好京客API与京东默认PID申请教程 京东API注册测试账号
- Ubuntu中snap是什么意思?介绍一些常用命令|焦点播报
- LOL各英雄的原型来源你了解几个? LOL背后的小故事
- 如何在excel中画斜线?在excel中画斜线的方法|天天新消息
- 激光焊接机价格怎么样?激光焊接机价格参考_世界滚动
- 全球滚动:电烤箱烤羊肉串怎么做?电烤箱烤羊肉串做法步骤
- sd卡数据恢复软件有哪些?sd卡数据恢复的软件
- 手机多媒体没声音是怎么回事?手机多媒体没声音怎么修?
- ISO9000和ISO9001有什么特点?ISO9000和ISO9001作用详解_环球头条
- 抖音可以查访客记录吗?抖音访客记录怎么看?
- 当前焦点!DOTA2前EG队长Fly求婚成功 晒出甜蜜合影
- 小键盘指法怎么操作?小键盘指法练习技巧|当前快播
- Windows 11壁纸有新玩法 用户可以自己画 焦点简讯
- 手机闪存卡哪款好?经典手机闪存卡有哪些推荐?|信息
- 电阻式触摸屏好用吗?电阻式触摸屏工作原理|全球信息
- 人生中的第一个Java程序:HelloWorld:天天百事通
- 爱宁牌电饼铛怎样?爱宁牌电饼铛的优势介绍
- vice versa是什么意思?vice versa通常翻译 世界快播
- 《冷漠 鸣神学园的七大不可思议》大型DLC12月23日上线
- 视讯!文件删除了怎么恢复?文件删除了三种恢复方法
- 联想服务器linux系统raid驱动 IntelRAID 6.12版RAID卡驱动官方正式版下载
- 全球快看点丨这款国产操作系统界面竟与Windows 11如出一辙
- 【环球快播报】除了币安,币圈最危险的大麻烦:稳定币USDT
- 浏览器市场占有率排行表 2020年8月国内浏览器排行
- GSC将推出上坂堇可动手办:声优首次figma化!
- 笔记本电脑品牌有哪些推荐?五款热门品牌推荐-焦点滚动
- 英特尔发力 游戏本将迎来24核心处理器-即时看
- 焦点速看:有哪些好看的电影推荐?吐血推荐250部必看电影
- 看热讯:华为荣耀4C详细评测 再次刷新安卓手机性价比
- 天天热推荐:Windows 11整个桌面将可做白板使用?
- 浏览器市场占有率排行表 2020年8月国内浏览器排行
- AssemblyInfo.cs文件的作用是什么?AssemblyInfo.cs文件详情
- 全球微资讯!咸鱼Maya笔记 Maya界面是怎么组成的?
- 南阳五中2021年高考成绩查询时间 南阳市五中举行2021年春期开学典礼
- 联想服务器linux系统raid驱动 IntelRAID 6.12版RAID卡驱动官方正式版下载
- 我们为什么要上学?奥巴马开学演讲稿:全球今热点
- 人工智能算法是什么?简化图形文件_全球视讯
- 宾得镜头简介 镜头术语都有哪些?|天天实时
- 安卓怎么开启启动模式?Android四种启动模式_环球速读
- 我的世界android制作教程 我的世界怎么去月球?
- APP(ios、Android)实现充值的方案 ios中充值功能的2种方案
- vice versa是什么意思?vice versa通常翻译 世界快播
- 电阻式触摸屏好用吗?电阻式触摸屏工作原理|全球信息
- Cubase延音踏板怎么设置?Cubase延音踏板设置延音效果 最新消息
- 人生中的第一个Java程序:HelloWorld:天天百事通
- 焦点速看:有哪些好看的电影推荐?吐血推荐250部必看电影
- 看热讯:华为荣耀4C详细评测 再次刷新安卓手机性价比
- 世界热点!计算机拨号连接无法建立连接怎么办?电信拨号上网连接不上的解决方法
- E. Border是什么?拓展欧几里得+mod分析
- 520还在画玫瑰?教你用MATLAB画个玫瑰花球|实时焦点
- 热门看点:币安将以10.22亿美元的价格收购加密货币借贷平台Voyager的资产
- IPO大潮退去,美股繁盛时期上市的大批股票现在面临退市风险
- 卡梅隆封神往事:一个天才疯子和《阿凡达》的20年_世界实时
- 神谷英树将《猎天使魔女:起源》比作童心绘本-全球播报
- Steam喜加一:圣诞主题像素排球游戏《Jollyball》
- 《碟中谍7》官方幕后花絮:阿汤哥太拼 3000米飞车跳崖|全球快播报
- 联想USB 3.0扩展坞29元限时秒:4个USB接口 支持Type-C供电-世界热点
- 苹果新一代显示器来了:屏幕升级为mini LED
- NVIDIA CES新品发布会官宣:RTX 4070 Ti、RTX 40笔记本显卡要来了:热门看点
- 性价比还得看AMD 6核锐龙+显卡+主板套装1239元:当前要闻
- 环球快消息!ZOL科技早餐:骁龙8 Gen2新机2999元,魅族19外观将揭晓
- 《水浒风云传》确定12月22日登陆Xbox和Switch 天天观速讯
- 【天天新视野】《原神》剧情视频「秋津羽戏」讲述人与妖的友情
- 高手用虚幻5做出《刺客信条》粉丝最期待的游戏功能