National's Day 听课笔记

Note

听课笔记
存图： 如果数据为$1 <= N, M <= 100000$ 那么可以使用前向星。但是如果碰到了$1 <= N <= 100$之类的数据范围可以考虑使用邻接矩阵。
最短路：
$Dijkstra${
朴素: $O(N^{2} + M)$
STL堆优化： $O((N + M)logM)$
手写堆优化：$O((N + M)logN)$
斐波那契堆：$O(NlogN + M)$
}
$Spfa$ : $O(VE)$到$O(NM)$。

出现负权边：只能用$Spfa$。
没有负权边：最好用堆优化$Dijsktra$。

生成树：
最小生成树{
$Kruskal$：$O(MlogM)$
$Prim$: $O((M + N)logM)$ 不一定要掌握
}
次小生成树：{
首先：一个有$N$个点的完全图，生成树个数为$N^{N- 2}$（由矩阵树定理$Matrix$ $Tree$ $Theory$）
先求最小生成树。枚举删掉最小生成树上的哪一条边。然后全图还剩下$M - 1$条边，然后接着跑最小生成树。那么时间复杂度为$O(NM)$。大概可以拿$60$分。然后满分做法是先加进来一条边，然后删去一条原来的最小生成树上的最大的那条边。而我们先加边会导致形成一个环包含加进来的这个边的两个端点，那么为了使它再次形成一棵树，我们就要再这个还上删掉一个边，那么我们就可以用倍增$LCA$进行删边。这样大概可以的全分了。
}

强连通分量：
有向图：
无向图：{
点双连通分量：割点
边双联通分量：桥
}

目的： 把有向有环图变成$DAG$进行$DP$。

DAG上 + DP + Topu
将图进行拓扑排序使边有序，那么我们就可以进行Dp.

网络流：胡伯涛最小割模型

二分图：{
常见的二分图：{
树： 按照奇数点和偶数点成二分图。
网格图：按照黑白点成二分图。
}
匈牙利匹配：上限$O(NM)$。
}