XUDJY

图论

C++(2) CF(32) CSP(3) ICPC补(3) QT(1) 动态规划(3) 数据结构(3) 数论(1) 树(9) 碎碎念(3) 算法基础(9) 题解(4)

/ 注册

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

Codeforces Round #586-E

题意：一个人在原点s，每个城市有对应的评价值w，不能走上次刚走的点，比如最开始从6-2，下一次不能立即从2-6，但可以通过绕一圈6-2-1-3-4-2-6的方式回到6，意味着每个节点每条边都有可能经过多次，每个节点只算第一次经过时候的值。求他在整个图中经过的城市累积的评价值的...

Trajan

2019-10-05

0 480

Prim与Kru，Dij与SPFA

1.SPFA,kruskal在稀疏图上有优势。 2.dij，prim稠密图上占优。 3.dij不能处理负边权（被坑了好多次啊啊啊啊啊），SPFA可以。 4.Dij与Prim两种算法本质是相同的,都是从某一个点开始进行延伸，不断更新一个dis值，直到所有的点都被遍历到，从而求出一个最...

Prim Dij SPFA Kru

2019-09-10

0 631

Floyd

算法介绍弗洛伊德算法是运用动态规划思想解决多源最短路的一种算法，可以正确处理有向图或负权（但不可存在负权回路这家伙无法判断负权)的最短路径问题，同时也被用于计算有向图的传递闭包。代码看起来很简短，但为啥说他是个动态规划呢？因为这其实是一个三维动归问题，...

Floyd

2019-09-09

0 612