Day24h

图论

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章 / 图论（共4篇）

Roadblocks

Roadblocks 该题的难点在于求次短路，而次短路的求法与最短路基本一致，更新的方式就是当当前权重比最短路大且比次短路小的时候就更新它，如果它比最短路小，那么就把它和最短路交换一下关键代码： //d1[i]是从起点到达i的当前最短路 //d2[i]是从起点到达i的当前次短路 i...

次短路

2020-01-18

0 558

路径还原

路径还原例如在求解最短路等等问题时，只需用一个pre[]数组在更新我们要求的数据时，记录一下前驱顶点即可

2020-01-18

0 451

Bellman-Ford

Bellman-Ford BF算法求的是单源最短路问题，即每一个点到起点s的最短距离。算法的思想在于\(d[i]=min(d[i],d[j]+e(j,i))\) d[i]表示点i到s的最短距离，对d[i]不断进行更新，知道不能更新为止，复杂度为\(O(nm)\) 代码： const in...

Bellman-Ford 最短路

2020-01-17

0 452

飞行员配对方案问题

P2756 飞行员配对方案问题参考：「网络流24题」 1. 飞行员配对方案问题思路：这是个二分图的匹配问题，虽然之前写过一遍了，再写一遍温习温习也无妨。使用匈牙利算法感觉参考博客中有一句话特别经典，很能描述匈牙利算法的思路..... 👇 👇 👇 👇 ...

网络流二分图匹配匈牙利算法

2019-10-05

0 387