BZOJ1001(对偶图+最短路)_对偶图最短路-程序员宅基地

技术标签: ACM  bzoj  图论_最短路  

1001: [BeiJing2006]狼抓兔子

Time Limit: 15 Sec   Memory Limit: 162 MB
Submit: 10398   Solved: 2376
[ Submit][ Status]

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

 

左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为N,M.表示网格的大小,N,M均小于等于1000.接下来分三部分第一部分共N行,每行M-1个数,表示横向道路的权值. 第二部分共N-1行,每行M个数,表示纵向道路的权值. 第三部分共N-1行,每行M-1个数,表示斜向道路的权值. 输入文件保证不超过10M

Output

输出一个整数,表示参与伏击的狼的最小数量.

Sample Input

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

14

题意:RT

思路:将这幅图转化为它的对偶图,然后跑从起点s到终点e跑一遍最短路即可,新图的边权为与原图交叉的边的边权

            如图:

#include 
   
   
    
    
#include 
    
    
     
     
#include 
     
     
      
      
#include 
      
      
       
       
#include 
       
       
         using namespace std; const int MAXN = 3000000; const int INF = ~0U>>1; int head[2000000]; int edge[MAXN<<1]; int w[MAXN<<1]; int next[MAXN<<1]; int esz; int E; void addedge(int u,int v,int w1) { edge[esz]=v; w[esz]=w1; next[esz]=head[u]; head[u]=esz++; } int dp[MAXN]; int vis[MAXN]; struct node{ int d; int u; node(int a,int b):d(a),u(b){} bool operator < (const node &a) const { return d>a.d; } }; priority_queue 
        
          q; void dj() { for(int i=0;i<=E;i++)dp[i]=INF; dp[0]=0; q.push(node(0,0)); while(!q.empty()){ node f=q.top();q.pop(); if(vis[f.u])continue; vis[f.u]=1; for(int i=head[f.u];i!=-1;i=next[i]){ int v=edge[i]; if(dp[v]>dp[f.u]+w[i]){ dp[v]=dp[f.u]+w[i]; q.push(node(dp[v],v)); } } } } int main() { int n,m,w; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); E=(n-1)*(m-1)*2+1; for(int i=1;i 
          
         
       
      
      
     
     
    
    
   
   
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cq_phqg/article/details/39975475

智能推荐

dom4j读取xml文档_获取xml行数-程序员宅基地

文章浏览阅读3.5k次。//book.xml Java就业培训教程 张孝祥 49.00元 34元 JavaScript网页开发 张孝祥 28.00元 package_获取xml行数

小学六年级上册计算机教学总结,小学六年级语文教学工作总结-程序员宅基地

文章浏览阅读140次。第1篇:六年级语文教学工作总结(六年级语文教学工作总结)武 莲 娣三 和 小 学 20XX 年 6月 20日六年级语文教学工作总结六年级第二学期是小学阶段的最后一学期,也是小学生学习道路上一个重要的转折点。为了使本届小学生能顺利完成小学阶段学习任务,确保毕业考试的全面丰收,我向课堂四十分钟..._六年级上册语文教学总结博客

Android Hybrid 学习过程 四 WebView所有相关类使用说明_android webview所有的dom-程序员宅基地

文章浏览阅读1.2k次。因为关于WebView的相关细节还有很多,我就不一一写例子说明,一口气全写出来凭注释说明了1.WebSetting用于配置WebVIew的类 WebSettings webSettings = mWebView.getSettings(); if (webSettings == null) return; //设置字体缩放倍数,默认10..._android webview所有的dom

牛客C基础题型复习打卡(2)_java题目描述:现在有人口渴了,要喝10升水才能解渴,但现在只有一个深 h 厘米, 底面-程序员宅基地

文章浏览阅读219次。乘风破浪会有时,直挂云帆济沧海。文章目录前言正文题目一:温度转换题目二:牛牛的圆题目三:牛牛的并联电路题目四:牛牛的水杯题目五:牛牛的等差数列题目六:小乐乐定闹钟题目七:肖小乐乐排电梯题目八: 小乐乐与欧几里得题目九:题目十:kiki算数结语前言forever 牛客C基础题型刷题复习训练营,从易到难,一遍一遍的刷题练习敲代码的习惯和思维,尽量使用熟悉的编程语言来敲。正文题目一:温度转换描述输入一个浮点数f, 表示华氏温度, 输出对应的摄氏温度.._java题目描述:现在有人口渴了,要喝10升水才能解渴,但现在只有一个深 h 厘米, 底面

layui 关于table详解(注释已在代码中详细介绍)_layui table-程序员宅基地

文章浏览阅读2.3k次。1.渲染table表格数据详解//渲染表格,classTable可以理解为表格里面所有的数据 var classTable = table.render({ // 提前准备好的table表格 elem: "#LAY-educationalTraining-gradeManagement-gradeInformation-table", // 表格里面的数据来源,返回的是分页数据Paging(Ipage ipage)_layui table

Kafka入门经典教程_kafka csdn-程序员宅基地

文章浏览阅读388次。http://www.aboutyun.com/thread-12882-1-1.html问题导读1.Kafka独特设计在什么地方?2.Kafka如何搭建及创建topic、发送消息、消费消息?3.如何书写Kafka程序?4.数据传输的事务定义有哪三种?5.Kafka判断一个节点是否活着有哪两个条件?6.producer是否直接将数据发送到broker的leade_kafka csdn

随便推点

[Hibernate开发之路](5)联合主键-程序员宅基地

文章浏览阅读97次。现在大家都不推荐使用联合主键,关键是因为其需要自己手工维护,比较麻烦。但是一个项目可能因为历史遗留原因,你不得不面对联合主键。Hibernate联合主键问题解决如下:可以使用一个组件作为一个实体类的标识符。你的组件类必须满足以下要求:(1)它必须实现 java.io.Serializable 接口(2)它必须重新实现 equals() 和 hashCode() 方法,始终和组合关键..._联合主键不能扫描basemapper

小米云网站服务器错误代码,Win11更新失败错误代码0x800f081f怎么办?-程序员宅基地

文章浏览阅读1k次,点赞2次,收藏2次。Windows11更新十分的勤奋,可以说每周都会更新一次,而不少用户在更新的时候却遇到一些问题,出现错误代码0x800f081f,导致更新失败。那么遇到这种情况我们要怎么解决呢?下面小编就带着大家一起来看看吧!操作方法:方法一:安装离线更新补丁下载对应的离线更新补丁,采用离线更新的方式。注意:.cab格式的更新包,应采用Dism++来安装更新。方法二:1、启动开始菜单,输入 “cmd”,右键以管理..._小米云盘系统错误如何改正

idea 热部署 jrebel 详细配置_查看jrebel 加载的jar-程序员宅基地

文章浏览阅读1.9k次。一、软件安装ideaIU-12.1.1.exe 下载地址: http://www.jetbrains.com/idea/download/index.html算号器:???要低调,用社区版吧,如果想用Ultimate版,自己找算号器吧。apache-tomcat-7.0.39(64)下载地址: http://www.apache.org/dist/tomcat/tomcat-7_查看jrebel 加载的jar

文献可视化工具(一)---VOSview_vosviewer安装包百度云-程序员宅基地

文章浏览阅读1.2k次。VOSview安装vosview下载官网:https://www.vosviewer.com/download百度网盘:链接:https://pan.baidu.com/s/1zj5ulxA2lsnuTFxVMRgnKw提取码:ifprvosview安装解压安装(前提是已经安装java),直接点击.exe即可运行..._vosviewer安装包百度云

RocketMQ入门(一)_rocketmq document-程序员宅基地

文章浏览阅读463次。今天的博客主题 MQ消息中间件 --》RocketMQ --》RocketMQ入门(一)本文主要了解认识RocketMQ对于新接触RocketMQ的同学来说 入门篇的五篇文章真的有必要好好看一下去理解它。我是之前了解过ActiveMQ,只是会应用,没有深入的了解。这个我想达到一个熟悉+的程度现在工作项目引入RocketMQ,必须深入了解精通,就结合官方的文档及源..._rocketmq document

CSS选择器小结(python使用css方式定位)_python可以用css来调节位置吗-程序员宅基地

文章浏览阅读1.3w次,点赞4次,收藏29次。学习Python写爬虫的时候,遇到css定位问题,故小结一下css选择器定位的方式通配符选择器:* {color:red;}CSS 类选择器匹配所有class = ‘important’*.important {color:red;}去掉前面通配符也是一样的。结合元素选择器匹配所有p标签下class = ‘important’p.important {color:red;}CSS 多类选择器匹配c..._python可以用css来调节位置吗

推荐文章

热门文章

相关标签