KetchupZ
KetchupZ
全部文章
# 最短路径/...
# 01_容斥定理(2)
# AC自动机/Manacher(8)
# color coding k-th近似算法(1)
# KMP(7)
# LCA(3)
# Prufer序列/无向图三元环计数(3)
# 凸包/旋转卡壳(2)
# 割点/割边/强连通分量(4)
# 区间DP(1)
# 单调队列/单调栈(6)
# 压缩算法(1)
# 回文自动机(3)
# 字典树(7)
# 字符串Hash(1)
# 实战项目(6)
# 并查集(2)
# 扩展欧几里得/中国剩余定理(3)
# 排序算法(5)
# 数位DP(8)
# 数论杂项(2)
# 最小生成树(3)
# 最小费用流(5)
# 朴素DP(1)
# 树形DP(4)
# 树状数组(11)
# 概率DP(3)
# 欧拉函数/素数(2)
# 欧拉路径/其他(1)
# 欧拉降幂(1)
# 状压DP(8)
# 线段树(2)
# 网络流/最小割/二分图匹配(10)
# 背包问题(6)
# 莫比乌斯反演(2)
# 语法/函数/部分骚操作(15)
++++++++几何数学++++++++(2)
++++++++数论++++++++(1)
+++++图论++++++++(2)
+++++字符串++++++++(1)
+++++数据结构++++++++(1)
+++++组合数学++++++++(7)
100场比赛计划(7)
cdq分治(1)
Codeforce(12)
专项之C/C++(13)
专项之Java(11)
专项之Liunx(1)
专项之sql(6)
专项之计算机网络(2)
其他题目/思维/贪心(42)
暴力/尺取/二分/三分(10)
未归档(11)
比赛历程(1)
比赛技巧(5)
深搜/广搜(5)
珂朵莉树/老司机树(1)
归档
标签
去牛客网
登录
/
注册
KetchupZ的博客
全部文章
/ # 最短路径/差分约束/最长路
(共12篇)
2019百度之星初赛第三场B题-最短路2(魔改dijstra)
百度之星初赛第三场B题-最短路2(魔改dijstra) 题目: 小 A 是社团里的工具人,有一天他的朋友给了他一个 n n n 个点,...
2019-08-24
0
475
洛谷P3953 逛公园(最短路+DP+冗余度+快速判零环)
P3953 逛公园 题目:传送门 思路: 定义⼀条路径 (X…Y) 的冗余度为它的长度减去 X…Y 的最短路长度,那么这题就是求1到N的冗余度小于k的路径的条数。我们定义 d ...
2019-07-31
0
525
差分约束&最短路小结
差分约束&最短路 什么是差分约束 如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组...
2019-07-18
0
634
POJ - 1364 (差分约束)
POJ - 1364 (差分约束) 题意: 给出一个数字序列 S={a1,a2,…an},它有 m 个子序列 Si={a[si], a[si+1], a[si+2], … a[si+ni]},现在给出 m 个限制条件:第 i 个子序列的和 < ki 或 第 i 个子序列的和 > ...
2019-07-18
0
433
HDU - 3592(差分约束)
HDU - 3592(差分约束) 题意: n个人编号分别是1…n在排队,排队顺序与序号相同。现在有x个喜欢关系和y个厌恶关系 对于每一个喜欢关系 :a b c 代表编号a和编号c之间的距离需要<=c 对于每一个厌恶关系:a b c 代表编号a和编号c之间的距离需要>=c 问在能...
2019-07-18
0
512
POJ - 1716 (spfa差分约束)
POJ - 1716 差分约束 题意: 给出n个区间,现在要你找出一个点集,使得这n个区间都至少有2个元素在这个点集里面,问这个点集最少有几个点 第一行一个整数n。 接下来n行,每行两个整数a,b,表示区间的左端点和右端点,被空格隔开。 所有输入数据的范围[0,10000] 输出集合最小的大...
2019-07-18
0
389
HDU 1688 Sightseeing(DP,统计最短路和次短路的个数)
HDU 1688 Sightseeing(DP,统计最短路和次短路的个数) 题目: https://cn.vjudge.net/problem/30153/origin 题意: 给定一个图,源点s和汇点t,统计s到t的最短路的个数和最短路长度+1的路的个数 思路: 如果只是统计s...
2019-07-18
0
561
J - Invitation Cards
待更新.......... 题目: In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. Th...
2018-09-18
0
492
最短路四大算法证明以及分析(Flord Bijkstra Bellman-ford SPFA)
此博文不具体给出其算法的代码,只对其中算法进行分并且给予证明 PS:这些算法我不用证明都是它是正确的(上世纪的数学家看着这些都不用证明,为啥,很简单的),但是我坚持重新证明一遍实际是为了加深印象,并且理解其中的道理和思想,这样在以后的运用中才能灵活运用,当然证明这些算法也 算法一:Flor...
2018-01-29
0
788
M - 昂贵的聘礼
年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:"嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。如果你能够弄来他的水晶球,那么只...
2018-01-28
0
415
首页
上一页
1
2
下一页
末页