Background: 当负权存在时,最短路不一定存在。如果最短路存在,一定存在一个不含环的最短路。 理由如下:在边权可正可负的图中,环有零环、正环和负环三种。如果包含零环或正环,去掉以后路径不会变长;如果包含负环,则意味着最短路不存在。(路径可以一直在负环中循环,则权值会无限小) 既然不含环,则最短路最多只经过(不算起点)个结点,可以通过 轮松弛操作得到。代码如下(起点为0): for (int i = 0; i < n; i++) d[i] = INF; d[0] = 0; for (int k…

2018年10月28日 0条评论 7点热度 阅读全文

今天再讲点跟N皇后有关的问题,骑士遍历问题,或者象棋中马的遍历问题,当然这里的马是国际象棋了,两者有着很多相似点,同时又有很多不同点,主要还是限制路径的区别,N皇后主要是自由放置只要满足条件就好,马的遍历则跟上下遍历的路径有关了,主要运用了图算法之深度广度遍历,以及图的建立等算法。 要求:实现棋盘上任意位置的一个棋子马,使它不重复的走过棋盘上的每一个棋盘格 分析:首先知道马在棋盘是怎么走的,根据国际象棋规则,马在一个起始位置共有8个可用的行动位置,当然边界方面需要另外考虑,我们的马的行走必须考虑这8种类可能性,排除…

2016年8月16日 0条评论 7点热度 阅读全文

圣诞前夜讲点比较具有圣诞感觉的算法,背包问题算法,这里我写了经典算法和贪心算法两种解决方法,因为时间不多,所以给出的数组是已经排序的,因为贪心算法可能要用得到,经典算法因为是一个一个比较,因此排序也就没有那么重要了,可能两种算法的最终运行效果一样的,朋友们调试的时候记得修改我给出的测试数组,今天实在太忙了,贪心使用的排序算法没有写,留着以后给大家讲排序算法的时候使用吧,圣诞快乐,诸位朋友们。 背包问题:就是现在有一个容量为PSIZE的背包,同时又有N件item,现在要求将这些item放入这个背包里面去,要求尽量放一…

2016年8月16日 0条评论 7点热度 阅读全文

圣诞前夜讲点比较具有圣诞感觉的算法,背包问题算法,这里我写了经典算法和贪心算法两种解决方法,因为时间不多,所以给出的数组是已经排序的,因为贪心算法可能要用得到,经典算法因为是一个一个比较,因此排序也就没有那么重要了,可能两种算法的最终运行效果一样的,朋友们调试的时候记得修改我给出的测试数组,今天实在太忙了,贪心使用的排序算法没有写,留着以后给大家讲排序算法的时候使用吧,圣诞快乐,诸位朋友们。 背包问题:就是现在有一个容量为PSIZE的背包,同时又有N件item,现在要求将这些item放入这个背包里面去,要求尽量放一…

2016年8月16日 0条评论 7点热度 阅读全文

今天把背包刷完了,无聊。。所以学习了新算法bellman-ford算法,这个模板是我照书打的,bellman-ford算法的主要用于在有负权值的情况下,求解单元最短路的方法,这个算法的主要思想就是不断的枚举从初始点到各个点的最短路,经过一条路到目标点,经过两条路到目标点,最多经过n-1条路到目标点就可以求解出最短路。 这样呢,我们有一个递推公式: 初始:dist[u] = Edge[v0][u]; 递推:dist[u] = min(dist[u-1],min(dist[j]+Edge[j][u])) j = 0,1…

2015年4月23日 0条评论 6点热度 阅读全文

字符串的特征向量就是由字符串各位置上的特征数构成的一个向量。设字符串为P,令Pi为从字符串首字母到第i个位置的前缀,则字符串P的i位置上的特征数就是Pi的首尾非空真子串匹配的最大长度。例如:字符串abcdaabcab的特征向量是(0,0,0,0,1,1,2,3,1,2)。其中第5个位置的特征数是1,因为P5是abcdaa,首尾非空真子串能够匹配的就是a;而第7个位置的特征数是3,因为P7是abcdaabc,首尾非空真子串能够匹配的是abc。0位置上的特征数显然为0。暴力法求特征向量显然是非常耗时的,实际上可以基于这…

2015年3月30日 0条评论 9点热度 阅读全文

PS:最近工作比较忙,所以把以前在学校做acm的时候写的一些解题报告发出来 http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2327 题目大意:(如题) 输入输出:(如题) 解题思路:从开始数后一个数往后枚举,然后判断其是不是循环数,如果是就输出退出。   void transfer() //转换函数,将整数的每一位数提取出来 { int i; n=0; while(tmp>0) { i=tmp%10; tmp/=10; tmpstr[n]=i;…

2014年10月28日 0条评论 1点热度 阅读全文

Trie树,也称为字典数,前缀树,每个单词的每个字母按照顺序对应一个节点。有重合的前缀就共享节点。理想情况下(满的情况),假若所有的单词都是N长,则树共有N层,每层都是26个子节点。在程序上,将根节点编号为0,根节点不代表任何字符。 在程序的实现上,树可以用数组存储,也可以用指针实现,这里介绍简单的数组方法实现。 用一个child[i][j]保存节点i的编号为j的子节点序号,j对应26个字母,如果child[i][0] == 0,那么说明i节点下面没有a这个子节点。trie树中可以用 value[i]存储附加信息 …

2014年6月24日 0条评论 9点热度 阅读全文

    快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法,实际上诸如Matlab等科学计算软件都已经实现了FFT,只需调用相应的接口即可。在ACM里,FFT的典型应用就是大数的乘法或者多项式的乘法。顺便,如果题目规模不是很大,有关大数的运算推荐使用Java语言,使用java.math.BigInteger包完成;包括高精度运算,可以使用BigDecimal包完成。任何情况下,会一门外语总是很重要的!     傅里叶变换一般指的是连续傅里叶变换,其定义如下: …

2014年6月18日 0条评论 5点热度 阅读全文

- -  更多关于tarjan算法扩展请关注   使劲戳→ tarjan算法扩展 题意: 给定有向图,问是否满足任意两点 x, y 使得 x->y 或 y->x 存在一条路径。 即 若缩点后新建图拓扑排序,图为单一的一条路径时,则输出Yes,反之No. tarjan+缩点+拓扑排序 //拓扑排序,每次输出只能输出一个节点的时候(只有一条路),则为yes 附代码: <pre name="code" class="cpp">#include <iostream…

2014年5月12日 0条评论 5点热度 阅读全文