POJ_3159_(数组模拟邻接表) POJ 3159 题意：题目告诉我们求点1和点n之间在满足约束条件dist[a]+c>=dist[b]时的最大差值, 假设三角形abc,起点是a,a->b(2) a->c(4) b->c(3),当a点糖果数是0时,如果走a->b->c得到c糖果数为5,不满足a->c(4)的要求,所以转换为有向图,求最短路 vector邻接表不行,用数组模拟邻接表12 2019-07-09 算法
POJ_1511_(dij/bellmanford) POJ 1511 题意：求每个点去1点的时间和回来时间的最小值,回来的最短时间就是点1到每一个点的最短路径,那么每个点去点1的时间呢？单独求每个点到点1时间肯定超时 将所有有向边都反向,在求点1到每个点的最短路径就相当于去点1的时间 主要是数据量太大,只能用邻接表存图,关键在于邻接表的构建 bellmanford1234567891011121314151617181920212223 2019-07-09 算法
POJ_2240_(bellmanford+floyd)/hash POJ 2240 与POJ 1860 一样, 判断是否存在 正权环 将字符串hash成[1,30]之内的顶点, bellmanford通过松弛次数来判断是否存在环, floyd通过比较2次货币流通后的任意一点(点就是货币)的值是否增加,增加了就说明存在正环 bellmanford1234567891011121314151617181920212223242526272829303132 2019-07-08 算法
POJ_3660_floyd POJ 3660 题意：告诉所有奶牛的关系,让你确定奶牛的排名(只有当该奶牛与其他所有奶牛的关系确定了才能确定该奶牛的排名) 通过floyd确定一个点是否能到另一个点.12345678910111213141516171819202122232425262728293031323334353637 #include <iostream>using namespace std;co 2019-07-08 算法
POJ_1502_最短路模板 POJ 1502 题意:求最短路中的 最大值 ，模板题 dij12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 #include <iostream>#include <string.h>#in 2019-07-08 算法
POJ_3259_spfa 6 POJ 3259 题意：能否通过负边回到过去，意思是求是否存在负权环. 开一个cnt[]记录每一个点访问的次数,如果存在负权环那么一定能一直松弛 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646 2019-07-08 算法 spfa
POJ_1860_判断正权环(bellmanford和floyd) 5POJ 1860题意：货币种类是点,货币交换是边,能否在交换回来使得金钱变多,意思就是是否存在正环 两层循环 模拟一次流通后 每一个点 的金钱数 将第一次多次循环和第二次比较，若有任意一个点钱数变多则说明存在正环123456789101112131415161718192021222324252627282930313233343536#include <iostream>us 2019-07-07 算法
HDU_1874_SPFA模板 原理： 在有向图中,对于某个边(u,v,w),若存在dist[v] < dist[u]+w,满足三角关系， 若所有边都满足此不等式,说明一个点已经无法通过任意联通点来松弛它,则所有的dist就是最短路 来源： 与 dij不同的是,bellman-ford基于迭代思想 spfa是队列优化的bellman-ford 流程： 将源点加入队列, 取出队头,扫描所有出边(u,v, 2019-07-07 算法 spfa
正则表达式 grep:Basic Regular Expression基本正则表达式 egrep:Extended grep扩展正则表达式 fgrep:Fast grep 声明:大部分都能在BRE中用, 通配符.,空行不能跳过 小数点.转义\. \w找到0-9数字和a-z或者A-Z字母和_下划线 \W是\w的补集,其他的符号都能找到 \d匹配所有数字,同理\D匹配所有不是数字的(补集) \s匹 2019-07-06 Linux学习
linux下c语言编译过程及gcc/g++区别 gcc与g++分别是c/c++的编译器.区别: 后缀为.c的文件,gcc当做c程序 g++当做c++程序,后缀为.cpp的两者都认为是c++程序.应为c++语法更严谨,所以g++可能编译不了c程序 gcc可以编译c/c++程序,但是gcc只能编译,不能自动和c++程序使用的库连接,所以通常使用g++来完成c++程序的编译和连接 有多个c源文件可用一下命令:gcc -o functi 2019-07-06 Linux学习