首页 >  
搜索关键字:无向图    ( 2981个结果
图的割点
传送门:https://www.luogu.org/problem/P3388 还有两点要注意的 1.割点可能有很多个 2.无向图和有向图都有割点 然后我们来看一看如何实现割点 方案一:枚举去掉每个点的情况,DFS判断时间复杂度O(n^2) 方案二:Tarjan实现 同样是用dfn表示搜索次序,但是 ...
分类:其他   时间:2019-10-20 17:02:23    收藏:0  评论:0  赞:0  阅读:3
使用Tarjan进行缩点无向图
int From[maxn],Laxt[maxn],To[maxnG[maxn]; int dis[maxn],S,T,ans; void add(int u,int v) { Next[++cnt]=Laxt[u]; From[cnt]=u; Laxt[u]=cnt; To[cnt]=v; } v ...
分类:其他   时间:2019-10-19 21:14:18    收藏:0  评论:0  赞:0  阅读:2
欧拉图Eulerian Graph
一、节点的度 无向图: 节点的度为该节点所连接的边数 有向图: 节点的度分为入度和出度。 二、欧拉图定义 具有欧拉回路的图称作欧拉图,具有欧拉路径而无欧拉回路的图称为半欧拉图。 欧拉回路: ? 通过图中每条边且只通过一次,并且经过每一顶点的通路。 欧拉路径: ? 通过图中每条边且只通过一次,并且经过 ...
分类:其他   时间:2019-10-19 20:57:33    收藏:0  评论:0  赞:0  阅读:1
求 无向图的割点和桥,Tarjan模板
/ 求 无向图的割点和桥 可以找出割点和桥,求删掉每个点后增加的连通块。 需要注意重边的处理,可以先用矩阵存,再转邻接表,或者进行判重 / const int MAXN = 10010; const int MAXM = 100010; struct Edge { int to,next; bool ...
分类:其他   时间:2019-10-19 20:40:47    收藏:0  评论:0  赞:0  阅读:2
POJ-3662 通信线路
摘要:简单来讲就是在无向图上求出一条从1到N的路径,使路径上第K+1大的边权尽量小。 第K大的尽量小,这种表述就容易让人想到二分。 蓝书上的解释:因为支付的钱更多时,合法的升级方案一定有包含子花费更少的升级方案,所以答案具有单调性。 那么我们只要把权值大于mid的路径权值设为1,小于mid的置为0, ...
分类:其他   时间:2019-10-19 19:41:03    收藏:0  评论:0  赞:0  阅读:1
最小生成树计数 模板 hdu 4408
题意是给定n个点,m条边的无向图,求最小生成树的个数对p取模。 用kruscal计算最小生成树时,每次取连接了两个不同联通块的最小的边。也就是先处理d1条c1长度的边,再处理d2条c2长度的边。长度相同的边无论怎么选,最大联通情况都是固定的。 分别对ci长度的边产生的几个联通块计算生成树数量再乘起 ...
分类:其他   时间:2019-10-19 11:30:52    收藏:0  评论:0  赞:0  阅读:0
在加权无向图上求出一条从1号结点到N号结点的路径,使路径上第K+1大的边权尽量小
二分+最短路算法 ...
分类:其他   时间:2019-10-17 23:00:46    收藏:0  评论:0  赞:0  阅读:1
[USACO19JAN]Grass Plantin
本人水平有限,题解不到为处,请多多谅解 本蒟蒻谢谢大家观看 题目:传送门 乍一看,用dfs遍历树在七搞八搞,最后怀着激动的心情提交,AC三个点,TLE七个点 30分代码: 仔细一想,这不就是统计树上点的度吗? 因为是无向图,所以 入度==出度 ,直接类似于桶排,因为只要有需要统计的数出现,我们记一个 ...
分类:其他   时间:2019-10-17 21:15:37    收藏:0  评论:0  赞:0  阅读:2
图的深度优先和广度优先遍历
深度优先遍历   首先我们说一下邻接点的定义,对于无向图,如果两个顶点之间相互连接,那么它们互称为邻接点。   深度优先遍历支持从指定的结点开始遍历。深度优先遍历,也称作深度优先搜索,缩写为DFS。深度优先遍历从某个顶点v出发,访问此顶点,然后从v的未被访问的 ...
分类:其他   时间:2019-10-17 20:16:39    收藏:0  评论:0  赞:0  阅读:3
图数据类型的定义
图 介绍   图是相较于树更复杂的一种数据结构类型,它表示了多对多的对应关系。图的结构其实就是一些顶点和一些边的集合。图又分为有向图和无向图。存储图的方法有很多,比如使用邻接矩阵,邻接表,十字链表和邻接多重表等等。下面我们一一介绍一下这些内容。 图的结构: 无向图: 无向图其实就 ...
分类:其他   时间:2019-10-17 19:39:12    收藏:0  评论:0  赞:0  阅读:4
向图中增加结点
向图中增加结点   我们前面说过采用邻接矩阵来存储图,那么向图中增加结点其实只需要改变顶点数目,以及在邻接矩阵中增加点与点,点与边的关系即可。 先看增加结点的函数   就是向函数中传入结点,判断图如果未满就将其存入存放结点的数组,然后给节点数目加一。 ~~~c ...
分类:其他   时间:2019-10-17 19:37:47    收藏:0  评论:0  赞:0  阅读:3
[ARC098F] Donation
问题描述 给定一张 n个点,m条边的无向图。这张图的每个点有两个权值 ai , bi 。你将会从这张图中选出一个点作为起点,随后开始遍历这张图。你能到达一个节点 i当且仅当你的手上有至少 ai 元钱。当你到达一个节点 i后,你可以选择对这个点捐赠 bi 元。你需要对每个点捐赠一次。问你身上至少要带多 ...
分类:其他   时间:2019-10-17 12:19:33    收藏:0  评论:0  赞:0  阅读:5
Caocao's Bridges——桥模板题
题目链接 题意: 给出 n 个点 m 条边的无向图,输出权值最小的桥 题解: 桥模板题 如果无向图本身就已经是不连通的了,直接输出 0 即可 (用并查集判断一下) 因为存在权值为 0 的情况,因此如果求出来的最小权值桥的权值为 0 时,根据题意,输出 1。 注意处理重边 代码: #include < ...
分类:其他   时间:2019-10-17 09:40:52    收藏:0  评论:0  赞:0  阅读:4
Warm up——缩点、树上直径
题目链接 题意: 给出n个点和m条边的无向图,存在重边,问加一条边以后,剩下的桥的数量最少为多少。 题解: 把这个无向图缩点后会得到一个只由桥来连接的图(可以说这个图中的所有边都是桥,相当于一棵树), 然后我们只需要找出来这棵树的最大直径(即相距最远的两个点)。 因为如果我们把直径所在的两个端点连起 ...
分类:其他   时间:2019-10-16 22:13:06    收藏:0  评论:0  赞:0  阅读:2
2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)- D. Delivery Delays -二分+最短路+枚举
"2018 2019 ACM ICPC Nordic Collegiate Programming Contest (NCPC 2018) D. Delivery Delays 二分+最短路+枚举" 【Problem Description】 一座城市为无向图带权图,一号节点为披萨餐厅的位置,有$k ...
分类:其他   时间:2019-10-16 17:46:02    收藏:0  评论:0  赞:0  阅读:1
CF852D Exploration plan
题目描述 给定一张 $V$ 个点,$M$ 条边的边带权无向图,有 $N$ 个人分布在图上的点上,第 $i$ 个人在 $x_i$ 这个点上,定义从一个点走到另一个点的时间为所走的路径上所有边权之和,问至少过多久才可以满足至少有 $K$ 个点上有人。 数据范围: $1\le V \le600,1\le ...
分类:其他   时间:2019-10-16 10:54:42    收藏:0  评论:0  赞:0  阅读:29
【ARC098F】Donation
【ARC098F】Donation 题面 "atcoder" 题意: 给定一张$n$个点,$m$条边的无向图。这张图的每个点有两个权值 $a_i,b_i$。 你将会从这张图中选出一个点作为起点,随后开始遍历这张图。 你能到达一个节点 $i$当且仅当你的手上有至少$a_i$元钱。当你到达一个节点$i$ ...
分类:其他   时间:2019-10-15 18:42:27    收藏:0  评论:0  赞:0  阅读:18
luogu P5043 【模板】树同构([BJOI2015]树的同构)
题面: 树是一种很常见的数据结构。 我们把N个点,N?1条边的连通无向图称为树。 若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。 对于两个树T1和T2,如果能够把树T1的所有点重新标号,使得树T1和树T2完全相同,那么这两个树是同构的。也就是说,它们具有相同的形态。 现 ...
分类:其他   时间:2019-10-15 14:40:51    收藏:0  评论:0  赞:0  阅读:19
地铁出行路线规划实现
地铁出行路线规划 简述 语言:java 编程工具:eclipse 编码格式:utf 8 本次实验函数通过邻接矩阵保存txt文件读入的站点路径信息,使用广度优先遍历求出最短路径 本次实验函数功能包括查询站点信息,查询线路信息,查询最短路径。 程序主体 1.建图 建一个v个顶点的无向图,并使用addEd ...
分类:其他   时间:2019-10-15 01:25:03    收藏:0  评论:0  赞:0  阅读:35
[AMPPZ2014] Petrol
问题描述 给定一个n个点、m条边的带权无向图,其中有s个点是加油站。 每辆车都有一个油量上限b,即每次行走距离不能超过b,但在加油站可以补满。 q次询问,每次给出x,y,b,表示出发点是x,终点是y,油量上限为b,且保证x点和y点都是加油站,请回答能否从x走到y。 输入格式 第一行包含三个正整数n, ...
分类:其他   时间:2019-10-14 14:19:58    收藏:0  评论:0  赞:0  阅读:22
2981条   1 2 3 4 ... 150 下一页
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号