Cpp算法-图论-Kruskal
说明
ufs[], find(int), unionn(int, int)
并查集结构edge[]
链式前向星cmp(Edge, Edge)
边排序方案
实现
1 | const int maxn = 1010; |
ufs[], find(int), unionn(int, int)
并查集结构edge[]
链式前向星cmp(Edge, Edge)
边排序方案
1 | const int maxn = 1010; |
例:洛谷P3375
pre()
求前缀数组kmp()
匹配字符串
1 | char s1[1000010], s2[1000010]; |
例:洛谷P4305
hash[]
哈希表find(int x)
查找哈希表中 x 的位置push(int x)
将 x 插入到哈希表中check(int x)
查找 x 是否在哈希表中
1 | #define p 100003 |
例:洛谷P3370
1 | typedef unsigned long long ULL; |
1 | typedef unsigned long long ULL; |
1 | typedef unsigned long long ULL; |
1 | typedef unsigned long long ULL; |
n, m, G[][]
点数、边数、邻接矩阵dist[][]
每对顶点间路径长度pre[][]
每对顶点之间路径make()
建图
1 | const int maxn = 110; |
G[][]
邻接矩阵deg[]
度ans[]
欧拉回路n, e
点数、边数
1 | int G[maxn][maxn], deg[maxn], ans[maxn]; |
n, m
点数、边数head, edge[]
链式前向星ans[], ansi
路径、数组大小vis[]
记录make()
建图
1 | int head[maxn]; |
待完成
1 | graph LR |
!!! tldr “题目及注解”
求上图从 A 到 E 的最短距离
K: 阶段
D(XI,(X+1)J): 从 XI 到 (X+1)J 的距离
FK(XI): K 阶段下 XI 到终点 E 的最短距离
倒推:
K=4F4(D1)=3F4(D2)=4F4(D3)=3
K=5F3(C1)=min(D(C1,D1)+F4(D1),D(C1,D2)+F4(D2))=min(5+3,6+4)=8F3(C2)
n, m
点数、边数G[][]
邻接矩阵存图dist[]
路径长度pre[]
路径make()
建图
1 | const int maxn = 10010; |
1 | struct Edge |