纪中14日听课小结
0x00 绪言
还不错吧……
起码这个还能听懂一些……
0x01 二分图
定义：将所有点分为两个集合，且同一个集合内的点没有直接的边
可以有环。但是可以证明只有偶环，没有奇环。
奇环：由奇数个点构成的环
匈牙利算法
基于贪心，框架DFS递归
可求二分图是否为完美匹配，或者二分图的最大匹配。
例题
BZOJ4443 小凸玩矩阵
有一个n*m的矩阵，要取出n个数，且每行每列至多取一个。
问取出的第k大数最大是多少。
Algorithm
将每一行/列看做是一个点
分别放置两个集合中
求原图的最大匹配
最后二分mid查找kmin
（我也不知道我说的对不对……还是听听大佬的吧！）
小凸玩矩阵 是先二分答案 再将需要用的点跑二分图判断该答案是否成立
0x02 SPFA*
* SPFA是Shortest Path Fast Algorithm的缩写
作用：计算单源最短路径长度
架构：BFS广搜变形+队列优化
时间复杂度：O（VE）~O（E）
玄学优化：SLF：若队尾的SSSP<队首的SSSP，则将队首队尾元素交换
0x03 Johnson
几乎没什么人用
在Dijkstra（迪杰斯特拉）的基础上构建
多了每一个点的权重h
在图外新建一个点
且这个点到所有点的的距离皆为0
dist[u,v]=dist[u,v]+h（u）-h（v）
可以处理负权边
0x04 Prim
用来计算最小生成树（MST，Minimum Spanning Tree）
基于贪心
用邻接表存储边（结构体更好）
- 从任意一点开始
- 扫描MST所有出边，选用离当前MST距离（边权）最小的点加入MST（即优先用边权小的边）
- 标记此点（用bool数组）
暴力O（|v|2）
堆优化后O（|v|*log（|v|））
0x05 kruskal
克鲁斯卡尔
基于贪心
同Prim，用来计算最小生成树（MST，Minimum Spanning Tree）
用并查集来查看是否形成环
- 使用邻接表储存两点之间的边权
- 将所有边按照边权进行排序（从小到大）
- 每次选取最小边权的两点，查询这两点是否在同一集合内
- 若不在，则将这两点连接，并使用并查集merge（合并）这两点
- 重复3,4直到连了n-1条边（或只有一个点的祖先是自己），即所有点都在同一个连通分量中
平均时间复杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集。（百度百科）