『算法-ACM竞赛-图论』树的直径-DFS+树形DP模板
『算法-ACM 竞赛-图论』树的直径-DFS+树形 DP 模板图论–树的直径–DFS+树形 DP 模板#include <iostream> #include <cstring> using namespace std; //maxv：源点能到的最远点，maxdis:最远点对应的距离, const int maxn = 1e4 + 5; struct Edge {
『算法-ACM竞赛-图论』树上倍增法求LCA
『算法-ACM 竞赛-图论』树上倍增法求 LCA树上倍增法求 LCA我们找的是任意两个结点的最近公共祖先, 那么我们可以考虑这么两种种情况: 1.两结点的深度相同.2.两结点深度不同.第一步都要转化为情况 1，这种可处理的情况。 先不考虑其他, 我们思考这么一个问题: 对于两个深度不同的结点, 把深度更深的那个向其父节点迭代, 直到这个迭代结点和另一个结点深度相同, 那么这两个深度相同的结点的 L
『算法-ACM竞赛-图论』有向图强连通分量SCC（全网最好理解）
『算法-ACM 竞赛-图论』有向图强连通分量 SCC（全网最好理解）有向图强连通分量 SCC（全网最好理解）定义： 在有向图中，如果一些顶点中任意两个顶点都能互相到达（间接或直接）,那么这些顶点就构成了一个强连通分量，如果一个顶点没有出度，即它不能到达其他任何顶点，那么该顶点自己就是一个强连通分量。 做题的总结吧算是： 1.给定一个有向图，求有多少个顶点是由任何顶点出发都可达的： 图中只有一个
『算法-ACM竞赛-图论』最长路-洛谷P1807 最长路_NOI导刊2010提高（07）
『算法-ACM 竞赛-图论』最长路-洛谷 P1807 最长路_NOI 导刊 2010 提高（07）题目描述设 G 为有 n 个顶点的有向无环图，G 中各顶点的编号为 1 到 n，且当为 G 中的一条边时有 i < j。设 w（i，j）为边的长度，请设计算法，计算图 G 中<1，n>间的最长路径。 输入格式输入文件 longest.in 的第一行有两个整数 n 和 m,表示有 n
『算法-ACM竞赛-图论』最长路-基于SPFA的调整模板
『算法-ACM 竞赛-图论』最长路-基于 SPFA 的调整模板1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
『算法-ACM竞赛-图论』最短路径生成树（计数）模板
『算法-ACM 竞赛-图论』最短路径生成树（计数）模板图论–最短路径生成树（计数）模板#include<iostream> #include<cstring> #include<sstream> #include<cstdio> #include<algorithm> #include<queue> using namespa
『算法-ACM竞赛-图论』最短路径生成树计数+最短路径生成树
『算法-ACM 竞赛-图论』最短路径生成树计数+最短路径生成树最短路径生成树计数。我们应该先明白什么是最短路径生成树，不会戳这里。计数方法明显是要使用乘法原理计数，也就是说我们可以得出每一步的方案数再乘进答案中。 接下来考虑如何的出每一步的方案数，所谓方案数也就是对于每一个 D[i]D[i]D[i]可以从多少个 D[j]D[j]D[j]转移过来，那么显然，比较大的距离只能从比较小的距离转移过来。
『算法-ACM竞赛-图论』最短路径生成树与最小生成树
『算法-ACM 竞赛-图论』最短路径生成树与最小生成树虽然放在一起，但是他们两个除了都是树之外没有一点关系。最短路径生成树，就是 ROOT 根节点到达任意点距离最短的路径所构成的树，就是最短路径生成树。我画两个图给大家理解。最短路径生成树最小生成树这时候大家会发现，最短路径生成树不就是求完最短路之后，路径所构成的树吗，其实就是这样的。但是这里要明白一点，最短路径生树不唯一。我们举一个最简单的例子，