iiiiikun
iiiiikun
全部文章
spfa
bfs(11)
codeforce(2)
codeforces(49)
dfs(27)
dp(65)
icpc(2)
kmp(2)
kruskal(1)
min25(1)
stl(3)
三分(1)
二分(11)
二分图(3)
二叉树(2)
二叉树遍历(1)
倍增(1)
几何(1)
前缀和(6)
剪枝(1)
动态规划(2)
单调栈(1)
博弈论(1)
双指针算法(1)
双端队列(1)
唯一分解定理(1)
回文(1)
图论(4)
堆(1)
字符串(2)
尺取法(1)
差分(4)
差分约束(1)
并查集(7)
循环节(1)
快速幂(3)
思维(5)
思维题(6)
拓扑排序(2)
排序(1)
数位dp(3)
数位交换(1)
数学题(1)
数据结构(7)
数论(17)
最大子矩阵(2)
最小生成树(8)
最短路(17)
最长公共上升子序列(1)
有向图强联通分量(4)
未归档(8)
权值线段树(2)
构造(2)
枚举(2)
栈(1)
树形dp(4)
树状数组(3)
树的直径(1)
概率(1)
模拟(1)
模拟赛(1)
模拟退火(1)
模板(9)
欧几里得(1)
欧拉回路欧拉路径(1)
牛客多校(1)
状态压缩(1)
矩形面积(1)
矩阵乘法(1)
矩阵快速幂(1)
离散化(1)
筛素数(1)
线段树(4)
网络流(3)
背包(1)
菜鸟(14)
蓝桥(23)
蓝桥杯(2)
蓝桥训练(2)
贪心(11)
递归(1)
递推(2)
链表(2)
队列(3)
题解(2)
马拉车(2)
高精度(1)
归档
标签
去牛客网
登录
/
注册
iiiiikun的博客
老废物了
全部文章
/ spfa
(共3篇)
单源最短路扩展:创建虚拟源点
解题思路:题目大致意思是求在题目给出的点中离s最近的距离,其实我们可以创建一个虚拟源点让各个点到他的路径是0,spfa 0 就行了。 #include<bits/stdc++.h> using namespace std; const int N=1010,M = 50010; i...
2020-12-17
0
402
1165. 单词环
解题报告:这题可以用spfa判断正环的做法+二分来做,我们二分他的环的平均长度,看看能不能凑成环,如果暴力去把每个字符串变成一个点,总共会有1e5的点,可以优化一下,把整个字符串变成一条边,把前两个和后两个的单词字母映射成一个点,总共26*26个点,如果朴素去做会tle,那么要加个玄学优化,如果更新...
2020-12-17
0
480
spfa判断负环+01分数规划
解题报告:二分他们的商值,把每条边变成t[i]-mid*w[i],然后看是否存在正环。 #include<bits/stdc++.h> using namespace std; const int N= 1010 ,M=5010; int h[N],idx,e[M],ne[M]; ...
2020-12-17
0
467