-
2018-12-07 18:49:24
Problem Description
在古老的魔兽传说中,有两个军团,一个叫天灾,一个叫近卫。在他们所在的地域,有n个隘口,编号为1..n,某些隘口之间是有通道连接的。其中近卫军团在1号隘口,天灾军团在n号隘口。某一天,天灾军团的领袖巫妖王决定派兵攻打近卫军团,天灾军团的部队如此庞大,甚至可以填江过河。但是巫妖王不想付出不必要的代价,他想知道在不修建任何通道的前提下,部队是否可以通过隘口及其相关通道到达近卫军团展开攻击。由于n的值比较大(n<=1000),于是巫妖王找到了擅长编程的你 =_=,请你帮他解决这个问题,否则就把你吃掉变成他的魔法。为了拯救自己,赶紧想办法吧。
Input
输入包含多组,每组格式如下。
第一行包含两个整数n,m(分别代表n个隘口,这些隘口之间有m个通道)。
下面m行每行包含两个整数a,b;表示从a出发有一条通道到达b隘口(注意:通道是单向的)。
Output
如果天灾军团可以不修建任何通道就到达1号隘口,那么输出YES,否则输出NO。
Sample Input
2 1 1 2 2 1 2 1
Sample Output
NO YES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[1001][1001];
int visit[1001];
int f;
void DFS(int t,int n)
{
int i;
for(i=1;i<=n;i++)
{
if(visit[i]==0&&a[t][i]==1)
{
visit[i]=1;
if(i==1)
{
f=1;
return ;
}
DFS(i,n);
}
}
}
int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
f=0;
memset(a,0,sizeof(a));
memset(visit,0,sizeof(visit));
for(i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
a[u][v]=1;
}
DFS(n,n);
if(f==0) printf("NO\n");
else printf("YES\n");
}
return 0;
}更多相关内容 -
论文研究-基于多元数据的城市区域可达性评估模型.pdf
2019-07-22 22:59:13传统的区域可达性评估模型一般只支持GIS、GPS等单一数据作为可达性的评估依据,无法避免因外界因素的影响对区域可达性造成的评估不准确。针对此问题,以出租车GPS行车数据、时段、天气等多维数据作为区域可达性的... -
高速铁路区域可达性的影响.ppt
2021-10-01 12:55:37高速铁路区域可达性的影响.ppt -
可达性分析算法
2021-07-21 18:54:27可达性分析算法:也可以称为根搜索算法、追踪性垃圾收集。 相对于引用计数算法而言,可达性分析算法不仅同样具备实现简单和执行高效等特点,更重要的是该算法可以有效地解决在引用计数算法中循环引用的问题,防止...一 概念
可达性分析算法:也可以称为根搜索算法、追踪性垃圾收集。
相对于引用计数算法而言,可达性分析算法不仅同样具备实现简单和执行高效等特点,更重要的是该算法可以有效地解决在引用计数算法中循环引用的问题,防止内存泄漏的发生。
相较于引用计数算法,这里的可达性分析就是 Java、C# 选择的。这种类型的垃圾收集通常也叫作追踪性垃圾收集(Tracing Garbage Collection)。
二 思路
所谓 "GC Roots”根集合就是一组必须活跃的引用。
基本思路:
-
可达性分析算法是以根对象集合(GCRoots)为起始点,按照从上至下的方式搜索被根对象集合所连接的目标对象是否可达。
-
使用可达性分析算法后,内存中的存活对象都会被根对象集合直接或间接连接着,搜索所走过的路径称为引用链(Reference Chain)。
-
如果目标对象没有任何引用链相连,则是不可达的,就意味着该对象己经死亡,可以标记为垃圾对象。
-
在可达性分析算法中,只有能够被根对象集合直接或者间接连接的对象才是存活对象。
三 GC Roots 可以是哪些?
-
虚拟机栈中引用的对象
比如:各个线程被调用的方法中使用到的参数、局部变量等。
-
本地方法栈内 JNI(通常说的本地方法)引用的对象
-
方法区中类静态属性引用的对象
比如:Java类的引用类型静态变量
-
方法区中常量引用的对象
比如:字符串常量池(string Table)里的引用
-
所有被同步锁 synchronized 持有的对象
-
Java虚拟机内部的引用。
基本数据类型对应的 Class 对象,一些常驻的异常对象(如:NullPointerException、OutOfMemoryError),系统类加载器。
-
反映 java 虚拟机内部情况的 JMXBean、JVMTI 中注册的回调、本地代码缓存等。
四 总结
总结一句话就是,堆空间外的一些结构,比如虚拟机栈、本地方法栈、方法区、字符串常量池等地方对堆空间进行引用的,都可以作为 GC Roots 进行可达性分析。
除了这些固定的 GC Roots 集合以外,根据用户所选用的垃圾收集器以及当前回收的内存区域不同,还可以有其他对象“临时性”地加入,共同构成完整 GC Roots 集合。比如:分代收集和局部回收(Partial GC)。
如果只针对 Java 堆中的某一块区域进行垃圾回收(比如:典型的只针对新生代),必须考虑到内存区域是虚拟机自己的实现细节,更不是孤立封闭的,这个区域的对象完全有可能被其他区域的对象所引用,这时候就需要一并将关联的区域对象也加入 GCRoots 集合中去考虑,才能保证可达性分析的准确性。
五 小技巧
由于 Root 采用栈方式存放变量和指针,所以如果一个指针,它保存了堆内存里面的对象,但是自己又不存放在堆内存里面,那它就是一个 Root。
六 注意
如果要使用可达性分析算法来判断内存是否可回收,那么分析工作必须在一个能保障一致性的快照中进行。这点不满足的话分析结果的准确性就无法保证。
这点也是导致 GC进行时必须“stop The World”的一个重要原因。
即使是号称(几乎)不会发生停顿的 CMS 收集器中,枚举根节点时也是必须要停顿的。
-
-
基于出租车GPS大数据的城市区域间可达性评估模型.pdf
2021-09-07 20:33:25基于出租车GPS大数据的城市区域间可达性评估模型.pdf -
图论——可达性和最短路径
2019-11-15 10:57:46可达性和最短路径Abstract1. 可达性的定义1.1 可达性判定,只需要求出邻接矩阵的n-1次幂1.2 回路判定,只需要计算到邻接矩阵的n次幂2. 可达性判定定理2.1 可达关系的判定2.1.1 例2.1 可达性矩阵2.2 可达性矩阵的简洁...可达性和最短路径
Abstract
声明:本文只为我闲暇时候学习所做笔记,仅供我无聊时复习所用,若文中有错,误导了读者,敬请谅解!!!
图的同构参见我的语雀:图论:可达性和最短路径:https://www.yuque.com/jhongtao/mai/gmgf1g- 在很多时候我们关心的可能不是两个结点直接有多少条通路,而关心的是两个结点直接有没有通路,或者最短的通路
1. 可达性的定义
1.1 可达性判定,只需要求出邻接矩阵的n-1次幂
1.2 回路判定,只需要计算到邻接矩阵的n次幂
2. 可达性判定定理
2.1 可达关系的判定
2.1.1 例
2.1 可达性矩阵
2.2 可达性矩阵的简洁求法
2.2.1 例
3. 最短路径
3.1 短程线及距离
3.2 结点间距离的判定定理
3.3.1 例
- 在很多时候我们关心的可能不是两个结点直接有多少条通路,而关心的是两个结点直接有没有通路,或者最短的通路
-
湖北省公路网可达性对区域发展的关联度分析 (2014年)
2021-05-24 03:06:06可达性是衡量交通运输网系统有效性的重要指标,可达性的提高能有效推动区域经济的进一步发展。公路网的修建能够进一步优化区域路网、提高可达性、从而进一步协调区域经济发展。作者运用灰色关联分析,通过研究历年湖北... -
ArcGIS中可达性的实现
2019-03-24 11:37:43ArcGIS中可达性的实现,利用arcgis 实现区域可达性分析的具体步奏 -
基于GI S的徐州公路交通网络可达性研究 (2010年)
2021-05-22 10:28:40选用最短时间法以及最短距离法两种方法,对徐州区域的公路交通网络可达性及其空间格局进行计算分析,得出徐州区域的公路网络可达性呈现出同心环状分布的空间格局,且可达性由中心向外逐层递减;外围可达性分布较好区域向... -
基于公路网可达性的浙江省城市腹地划分研究 (2012年)
2021-05-21 21:10:54以浙江省11个地级市为研究对象,运用GIS技术,结合公路网可达性对浙江省的城市做出腹地划分,并对公路网与腹地的形成机制、腹地与行政区域的叠合做出了详细分析.基于公路发展形势的需要将舟山市列入研究范围,是对浙江省... -
基于GIS的西北地区交通网络可达性探讨
2020-02-25 05:16:16基于GIS的西北地区交通网络可达性探讨,邢钊,马金辉,为加强西北各省区域内部的资源整合与生产力要素合理配置,进而实现西北地区各城市间协调发展与经济腾飞,本文利用GIS技术,结合最新� -
移动传感器的基于电缆的移动可达性
2021-02-23 09:32:12当事件发生时,一些移动传感器需要移动到目标区域以进行进一步调查,在此可以重新放置其余的传感器,以保持该区域内可达性的平衡。 我们证明问题是NP难的,并提出了启发式算法来解决该问题。 证明了算法的正确性,... -
中国县域可达性区域划分及其与人口分布的关系
2012-05-07 00:24:08可以借鉴,挺好的。中国县域可达性区域划分及其与人口分布的关系,王振波 1 ,徐建刚 1 ,朱传耿 2 ,祁毅 1 ,徐璐 1 -
可视化城市可达性
2022-03-13 16:54:40可视化城市可达性可视化城市可达性
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
提示:这里可以添加本文要记录的大概内容:
参考教程:https://gitee.com/ni1o1/pygeo-tutorial/blob/master/15-.ipynb
可达性的度量方法:用路网节点到兴趣点的距离来度量;
(后期打算用每个小区到兴趣点的距离来度量)
提示:以下是本篇文章正文内容,下面案例可供参考
一、获取POI(兴趣点)
获取的平台:百度开放平台
import requests import json import pandas as pd """ 下面是获取poi的程序 """ def searchjson(query,region,page_num): params ={ "query":query, "region":region, "city_limit":False, "page_size":20, "page_num":page_num, "output":"json", "ak": '你自己的ak' } r = requests.get("https://api.map.baidu.com/place/v2/search",params =params,timeout =5) return json.loads(r.text)
pois = [] page_num = 0 while True: print("抓取分页:",page_num) decodejson = searchjson("医院","蔡甸区",page_num) if decodejson.get("results"): parks += decodejson["results"] page_num += 1 else: break print("抓取结束") df = pd.DataFrame(parks) df.to_csv("武汉市蔡甸区医院.csv") #保存文件
二、POI数据处理
1.查看location列的格式
发现location列对应的值是str;
需要先将str转换成dict,
在提取lat(精度) 和lon(维度)2.改变格式并生成lat lon列
import ast for i,v in df['location'].items(): #把str转换成dict v = ast.literal_eval(v) df['location'][i] = v df['lat'] =pd.DataFrame(df.location.to_list())['lat'] df['lng'] =pd.DataFrame(df.location.to_list())['lng'] df
三、可视化城市可达性
剩下的就主要就是按余庆学长的教程来
教程链接:https://gitee.com/ni1o1/pygeo-tutorial/blob/master/15-.ipynb
注意事项
1. 确定研究区域的边界
bbox = [30.43,113.8932,30.6231,114.3107] #经开区研究范围的大致经纬度,GCj-02坐标系
确定方式:
(1)确定区域
(2)导出
-
arcgis可达性分析
2020-05-14 17:08:18可达性用于测度区域内一点到最近旅游景点所花费的时间表征区内游客到景点的便利程度,有助于厘清旅游景点和交通网络之间的关系,计算公式如下: Ai = min ( MjTij ) 式中:i、j 为示范区内的景点;Tij 为点i ... -
基于交通可达性的上海郊区新城房价研究 (2010年)
2021-05-17 06:53:32基于公路交通可达性对上海郊区新城房价产生的时空影响进行研究。首先,选取上海郊区新城的住宅房价样本进行统计分析;其次,选择最快路径和最短路径2个指标,计算各郊区新城到上海中心城区外环线的可达性;最后,运用... -
java垃圾回收机制--可达性算法
2021-02-12 17:05:47先说一些题外话,Java...此区域是是唯一一个在java虚拟机规范中没有规定任何OutOfMemoryError情况的区域。b、Java虚拟机栈描述的是Java方法执行的内存模型,每个方法在执行的同时会创建一个栈帧c、本地方法栈它与... -
基于GIS的绿地景观可达性研究--以沈阳市为例 (2005年)
2021-04-21 23:01:50目的 利用GIS系统建立城市绿地可达性模型,评价绿地景观格局与服务功能,从而为城市绿地的规划、营建、格局优化、管理提供决策支持。方法 基于物理势能模型,以人口密度、道路分布、土地利用以及绿地面积作为模型... -
java 垃圾回收总结(可达性分析 引用分类
2021-02-28 19:25:07主要是class的一个内存结构信息 常量池:方法区的一部分,主要保存class内存结构中常量值 例如String值,public static final 类型的值 我们这里说的垃圾回收,主要是java虚拟机对堆内存区域的回收。 1 首先的问题是... -
论文研究-基于路网可达性的交通控制子区划分方法研究.pdf
2019-09-10 12:25:02为了提高子区划分的效率,保证子区划分结果的合理性,提出了一种基于路网可达性的子区划分方法。以路口为顶点,路段为边,修正的路段阻抗为边权得到路网加权网络,通过权系数开关化转为非加权网络;采用[K]步可达... -
GIS空间分析 栅格数据分析3 可达性分析
2022-04-26 21:34:18掌握栅格数据的可达性分析方法 -
垃圾回收之标记阶段-可达性分析算法
2022-04-30 16:52:16可达性分析算法 可达性分析算法:也可以称为 根搜索算法、追踪性垃圾收集 相对于引用计数算法而言,可达性分析算法不仅同样具备实现简单和执行高效等特点,更重要的是该算法可以有效地解决在引用计数算法中循环引用... -
jvm 可达性分析算法是怎么实现的?
2021-03-03 14:33:59在上一篇文章中,我们说到了jvm使用可达性算法来判断对象是否应该回收。可达性算法从特定的对象集合(即GC Roots Set)出发,逐一判断对象是否可达。具体来说,分成两个阶段:首先枚举所有GC Roots 对象,然后进行... -
jvm根节点枚举、安全点、安全区域、记忆集、卡表、写屏障、并发的可达性分析
2021-11-20 12:36:23也就是可达性分析算法从GC Roots集合中找引用链的过程,可作为GC Roots的节点主要在全局性的引用(例如常量或类静态属性)与执行上下文(例如栈帧中的本地变量表)中,虽然目标已经明确,但要逐个检查这里面的引用,... -
可达性分析算法GC Roots
2021-09-09 14:24:27当前主流的商用程序语言(Java、C#,上溯至前面提到的古老的Lisp)的内存管理子系统,都是通过可达性分析(Reachability Analysis)算法来判定对象是否存活的。这个算法的基本思路就是通过一系列称为“GC Roots”的... -
从数据获取到交通可达性分析【全流程】
2021-04-01 20:03:29嗨咯各位小伙伴们,小编又来跟大家分享GIS干货啦!今天呢,我们一起探讨一下ArcGIS中基于最小阻抗的交通可达性的完整流程,当然这个教程在其他许多公众号里都比较常见,所以今天小编会从数据获... -
引用计数法和可达性分析算法
2021-11-23 20:42:27垃圾回收的区域:方法区,堆 引用计数法 栈中有对堆中的对象有引用,如果失去了这个引用关系,那么这个对象就需要被回收 在引用计数法中当一个对象被引用时,这个对象的的计数值+1,失去引用时,计数值-1,当计数值... -
5-交通可达性计算原理与基础数据准备
2021-10-16 20:04:28数据处理:去除高速公路等不能平交的道路、山川湖泊等不可地形或极难同行区域(生成时间成本栅格) 【高速公路、铁路、山水湖泊及诸多限制要素 通过成本工具,带入数据计算 **结果校核:**通过百度地图进行 城市...