佛奴儿

分类

未归档(985)

/ 注册

TA的专栏 0篇文章 0人订阅

职场那些事儿

0篇文章 0人学习

全部文章（共985篇）

字符串hash-RK算法讲解二

算法分析：预处理时间Θ(m)，即求h,p,t的时间为，匹配时间在最坏情况下为Θ((n-m-1)m)，因为可能出现每次都是可能命中点的情况。如T=a^n,P=a^m，此种情况下验证时间为Θ((n-m-1)m)。当然实际中，可能的命中点一般很少。假设有c个，则算法的期望匹配时间为O(n-m+1 +cm)...

2018-08-09

0 545

字符串匹配&Rabin-Karp算法讲解

问题描述： Rabin-Karp的预处理时间是O(m)，匹配时间O( ( n - m + 1 ) m )既然与朴素算法的匹配时间一样，而且还多了一些预处理时间，那为什么我们还要学习这个算法呢？虽然Rain-Karp在最坏的情况下与朴素匹配一样，但是实际应用中往往比朴素算法快很多。而且该...

2018-08-09

0 545

POJ 3259 Wormholes【最短路/SPFA判断负环模板】

农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，...

2018-08-09

0 430

POJ 1860 Currency Exchange【SPFA判环】

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchang...

2018-08-08

0 795

如何判断图中存环（正&负）

1.正环用 SPFA不断的进行松弛操作，发现当前金额可以比本身大就更新，同时记录更新次数。如果更新次数超过n次，说明存在”正“环。 2.负环这里先说明下负环。（求最短距离的时候）在我们用SPFA求最短路径的时候，如果存在负环，在松弛操作的时候总会加入队列因为最小距离会越来越小，同...

2018-08-08

0 685

POJ 1797 Heavy Transportation 【最大生成树的最小边/最小瓶颈树】

Background Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him w...

2018-08-08

0 338

POJ 2253 Frogger【最短路变形/最小生成树的最大权/最小瓶颈树/A到B多条路径中的最小的最长边】

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but ...

2018-08-08

0 398

第K短路模板【POJ2449 / 洛谷2483 / BZOJ1975 / HDU6181】

1.到底如何求k短路的？我们考虑，要求k短路，要先求出最短路/次短路/第三短路……/第(k-1)短路，然后访问到第k短路。接下来的方法就是如此操作的。 2.f(x)的意义？我们得到的f(x)更小，优先访问这个f(x)的点。我们可以定义...

2018-08-08

0 407

HDU 3339 In Action【最短路+01背包模板/主要是建模看谁是容量、价值】

Since 1945, when the first nuclear bomb was exploded by the Manhattan Project team in the US, the number of nuclear weapons have soared across the ...

2018-08-08

0 267

链式前向星实现的堆优化dij求最短路模板

#include<cstdio> #include<string> #include<cstdlib> #include<cmath> #include<iostream> #include<cstring> ...

2018-08-07

0 356