CF-1217D Coloring Edges 题解

题目大意

小明是一个国王,他的国家有n个城市。

现在小明想为这n个城市制造m条路径(路径都是有向的),现在小明有k种不同种类的材料,可以用来制造路径。

无自环,无重复边。

在制造路径的时候,小明不想看到一个环的路径都是由一种材料制造成的,这样小明就会生气。

现在问你这个k最小值应该是多少呢。

阅读更多...

A*算法

基本介绍

把Dijkstra算法(靠近初始点的结点)和BFS算法(靠近目标点的结点)的信息块结合起来。在讨论A*的标准术语中,g(n)表示从初始结点到任意结点n的代价,h(n)表示从结点n到目标点的启发式评估代价(heuristic estimated cost)。

当从初始点向目标点移动时,A*权衡这两者。每次进行主循环时,它检查f(n)最小的结点n,其中$f(n) = g(n) + h(n)$。

A*主要作为寻路算法作用在游戏上。

阅读更多...

AC自动机

基本介绍

AC自动机,正如他的名字,能够让你自动AC(误

其实是一个匹配字符串的算法。

简单来说,就是在trie树上用KMP的思想。

(当然,你也可以理解为就是用了KMP。。

因为本来trie树是可以用来匹配字符串的,但是因为匹配失败的时候都需要从头开始,会导致浪费了很多时间,加大了时间复杂度。

所以,就提出来了AC自动机。

原理就是和KMP的next数组类似,使用一个fail数组,来记录匹配失败之后,需要回溯到哪个地方。

这样便能减少很多复杂度。

时间复杂度为$O(n)$($n$为文本长度)

(AC自动机怎么不能帮助我自动AC啊。。

阅读更多...
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信