Izayoi_w

未归档

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

/ 注册

全部文章 / 未归档（共34篇）

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-30

0 522

容斥原理

今年省赛被这个题坑了。。。才发现竟然不知道这个重要的知识。在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗...

2018-07-30

0 516

kuangbin一D：Fliptile （状态压缩DFS）

Describe: Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows i...

2018-07-24

0 446

kuangbin一B：POJ2251 Dungeon Master（BFS）

题目： You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with ...

2018-07-23

0 408

kuangbin一A：POJ1321 棋盘问题（DFS）

Description 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。每组数据的第一行是两个正整数，...

2018-07-22

0 435

数论学习（3）——中国剩余定理

中国剩余定理，又名孙子定理，最早出现于《孙子算经》上，是一种用于求解一元线性同余方程组的算法。引入例题： “今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？” ——《孙子算经》翻译成现代汉语就是：有一个整数x，x % ...

2018-03-18

0 464