Izayoi_w

分类

2019牛客多校(3) bfs(1) csdn博客(1) c语言(1) 个人刷kuangbin带你飞系列(3) 原创(4) 图论学习(1) 数论(1) 未归档(34) 计算机(1) 转载(1)

/ 注册

全部文章（共51篇）

最小生成树Prim算法与Kruskal算法

这两种算法是基于不同的角度得出的最小生成树算法，Prim是“加点法”，而Kruskal是“加边法”。下面让我们来看一看这两种算法的原理和具体实现。相关概念：连通图：在无向图中，若任意两个顶点与都有路径相通，则称该无向图为连通图。强连通图：在有向图中，若任意两个顶点与都有路径相通，...

2018-08-08

0 962

寂静之城

链接：https://www.zhihu.com/question/277522256/answer/396613033 来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。原作：马伯庸寂静之城美利坚合众国，2015年，纽约。　　当电话响起来的时候，阿...

2018-08-05

0 7814

kuangbin带你飞系列目录与简介

kuangbin带你飞系列是由ACM圈内的一个菊苣，上海大学的邝斌（现已研究生毕业，就职于谷歌），在vjudge平台上建立的一个题目系列，从最简单的暴力搜索，到各种高深的算法与数据结构，几乎无所不包，这一套刷下来对于每一位打ACM的人来说都将是一次水平的飞跃。目录链接：https://cn.vj...

2018-08-05

1 2033

kuangbin五A：POJ2236 Wireless Network（并查集应用）

Description： An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computer...

2018-08-03

0 472

并查集的实现及优化

并查集是一种用于在森林中判断子图数量及点的归属的数据结构，由于其特殊的路径压缩操作，使得这一过程可以异常地快。并查集主要由一个pre数组以及两个函数组成：find函数和join函数。 pre数组表示每一节点的前驱，最终已完成的并查集，每一个子图的所有点只有一个前驱（这也是其高效的原因），而初始化...

2018-08-03

0 504

Floyd-Warshall算法

说实话，在一开始没学的时候还觉得挺高大上的算法，学了之后发现，最短路四大算法，这是最暴力的一个。。 Floyd-Warshall算法，一般也叫Floyd算法，这个算法正如网传的那样：核心算法只有5行： for(int i = 1; i <= n; i++) for(int j = 1; j...

2018-08-02

0 548

Dijkstra算法及其优化（Dijkstra+heap）

Dijkstra(迪杰斯特拉)算法是一种经典的求单源最短路的算法，大体上就是利用已经找到的点的最短路去推其他点的最短路。我们先将图中的点分为两部分： S：已经找到最短路的点 T：图G - S，剩下的点具体过程如下：将dis数组初始化为INF，源点s，dis[s] = 0，s点加...

2018-08-01

0 406

SPFA算法以及其优化

SPFA算法（Shortest Path Faster Algorithm），是经队列优化的单源最短路Bellman-Ford算法通常用于求含负权边的单源最短路径，以及判负权环。SPFA算法最坏情况下复杂度和朴素的Bellman-Ford算法相同，为O(VE)，一般情况为O(kE)，其中k为常数，由...

2018-08-01

0 641

Bellman-Ford算法求最短路

图论中比较基础的问题，求单源最短路，即在图中找一个点作为起点，求他到其他点的最短路，而Bellman-Ford算法是其中最简单的算法，相应地，其复杂度也比较高，效率也比较低，但是，他却可以判断图中是否存在负权回路（走一圈经过的权值是负数），因此可以处理带有负权边的图，且该算法是其他各种最短路算法的原...

2018-07-31

0 433

链式前向星

我们在图论题目的代码编写中一般会涉及到图的储存问题，通常的存图的方法是邻接矩阵和邻接链表，这两者比较简单，不做过多介绍。不过，这两者一个当面对稀疏图时占的内存过大，一个因为是链表操作又太慢，而且链表的节点比矩阵的节点占内存大，节点一多一样很占空间，这两者都不是那种比较理想的存图方式，而链式前向星综合...

2018-07-31

0 632