Johnson全源最短路
由于dijkstra不能用于带有负边权的图,而Floyd算法的复杂度又过高,在处理稀疏图时往往耗时较… 继续阅读 Johnson全源最短路
Hello World
由于dijkstra不能用于带有负边权的图,而Floyd算法的复杂度又过高,在处理稀疏图时往往耗时较… 继续阅读 Johnson全源最短路
狄杰特斯拉定理不仅可以用来求最短路,同时也可以在同样的复杂度里完成次短路的计算。 核心在于开两个数组… 继续阅读 图上的严格次路径
狄尔沃斯定理(Dilworth’s theorem)是关于偏序集的极大极小的定理.该定理… 继续阅读 狄尔沃斯定理求链的划分
Biginteger大整数加乘模板 #include <bits/stdc++.h> u… 继续阅读 算法竞赛程序模板
Floyd算法核心片段如下: for(int k=1;k<=n;k++) { for(int … 继续阅读 Floyd算法的应用
费马小定理:任意整数a, a^p≡a (mod p),p是质数。 定理:1.对a/b≡a*x (mo… 继续阅读 费马小定理与等比数列的求和(mod 质数)
例题:GCD最大公约数 这道题中,要我们找到在1~N中找到数对(x,y)来使,gcd(x,y)=d,… 继续阅读 数论:欧拉函数的线性求取与应用
例题POJ2689Prime Distance 我们通过要求得一个区间[L,R]内的素数,由于L和R… 继续阅读 通过埃式筛法筛选区间素数
洛谷P1462通往奥格瑞玛的道路 设某条从 1 到 n 的路径里,经过单个城时所花费的费用的最大值为… 继续阅读 二分法+Dijkstra算法
例题链接:CF20C 我们通过了Dijkstra算法或者SPFA算法等等获得了最短路径,记为 d[ … 继续阅读 最短路径还原的实现方法