1、最短路
单源最短路
所有边权都是正数
朴素版Dijkstra O( n^2 );(n^2 <= m时使用)
堆优化Dijkstra O( m log n );(稀疏图)
有负权边
Bellman-Ford O(nm)
SPFA 一般O(m) , 最坏O(nm);
双源最短路
Floyd O( n^3 );
朴素版dijkstra
(1)memset( dist , 0x3f , sizeof(dist) ) dist[s] = 0;
(2)for ( i : n )
t -> 不在加入答案集合中的，距s最近的点
把t加入答案集合
用t更新答案
理解过程
如果没有负权，并且dist[a]>dist[b],那么b永远不会被a更新
所以如果dist[x]是最小的，那s到x的最短路就不会被更新
稀疏图用邻接表，稠密图用邻接矩阵，临界矩阵如果有重边记得取Min
https://www.acwing.com/activity/content/code/content/9366403/
堆优化dijkstra
就是把每个点的距离用堆存储就好
原来的时间复杂度
for ( i : n )O(n)
t -> 不在加入答案集合中的，距s最近的点O(n)
把t加入答案集合O(1);
用t更新答案O(n);
时间复杂度O(n^2)
现在的
while( !heap.empty() )O(n)
t -> 不在加入答案集合中的，距s最近的点O(1)
把t加入答案集合O(1);
用t更新答案O(log n);
在用堆优化实现的dijkstra用于稀疏图，所以遍历出边的时间复杂度基本可以忽略不记
https://www.acwing.com/activity/content/code/content/9366554/
Bellman-Ford
只适用于解决有边数限制的最短路问题，其他情况可以使用SPFA算法代替
这个算法其实很容易懂，伪代码
for ( i : 边数限制 )
for ( int j : m )
dis[e[j].v] =
min ( dis[e[j].v] , last[e[j].u] + e[j].w );
注意一下细节，如果在进行第i次遍历时用dis[a]更新dis[b],
被更新过的dis[b]再去更新dis[c]这里我们就用了2条边
所以要用last数组存上一次的状态
细节，判断不可达时要用dis[n] > 0x3f3f3f3f / 2,因为如果有一个点5,dis[5] = 0x3f , w( 5 , x ) = -2(dis[x] = 0x3f)
这里我们会用dis[5]把dis[x]更新成0x3f - 2;
https://www.acwing.com/activity/content/code/content/9366982/
SPFA算法
Bellman-Ford的优化
我们发现,在上面的代码中，只有dis[e[j].u]变小了,dis[d[j].v]
才有可能更新，所以我们可以用一个队列记录距离变小的点
用队列中的这些点进行更新
一个小优化就是可以不把目前在队列里的点再次加进去，只更新dis数组就行;
并且这题不需要0x3f3f3f3f / 2 , 因为队列中的点都是从起点更新到的点，不存在Bellman-Ford算法中未更新的点被边更新的情况
https://www.acwing.com/activity/content/code/content/9367230/
SPFA判断负权环
我们用cnt[i]表示从s走到i经过了几条边，我们发现如果
任意一个cnt[x] >= n，那么就一定不合法
因为经过超过n条边就走了至少n+1个点，如果重复走还可以是最短路，那么就存在负权环
这个东西也很好维护就是cnt[j] = cnt[i] + 1;
https://www.acwing.com/activity/content/code/content/9367581/
Floyd
非常简单
核心功能
for ( int k = 1 ; k <= n ; k )
for ( int i = 1 ; i <= n ; i )
for ( int j = 1 ; j <= n ; j++ )
dis[i][j]=min ( dis[i][j] , dis[i][k] + dis[k][j]);
就是对于一组i , j,找一个中转点k，看看是否距离变小就行
https://www.acwing.com/activity/content/code/content/9367971/
2、最小生成树
Prim算法
朴素版prim O(n^2)
堆优化primO(n log n)(一般不用)
kruskal算法
时间复杂度O(m log m)
算法选择
稠密图：朴素prim算法，稀疏图：kruskal算法
朴素Prim
最小生成树：用n - 1条边把图中的所有点连接起来，并且使边权之和最小，没有自环
类似于dijkstra;
dist <- 0x3f
for(i : n)
t <- 找到集合外距离最近的点
用t更新其他点到集合的距离
in[t] = true;
集合：在连通块当中的所有点
每个点到集合的距离：他所有能到集合中的边长度最小的一条
特判：所有点不连通时不存在生成树
有些细节在代码里
https://www.acwing.com/activity/content/code/content/9371295/
Kruskal算法
1、将所有边按权重从小到大排序O(m log m)
2、枚举每条边 a , b , w;O(m)
if( a、b不连通 )
将这条边加入集合
判断不连通可以使用并查集
https://www.acwing.com/activity/content/code/content/9371472/
3、二分图
染色法O(n + m)
匈牙利算法O(nm)，实际运行时间远小于O(nm)
定义：可以把所有点化分成2边，集合内部没有边
性质：二分图当且仅当图中不含边的数量为奇数的环
判断一个图是不是二分图：染色法
开始对一个未染色节点染色
如果其相邻节点没有染色就染上与当前节点的相反色
最后判断是不是一条边连接的2个点属于不同集合
使用dfs遍历就可以了
https://www.acwing.com/activity/content/code/content/9371597/
匈牙利算法
二分图最大匹配问题
形象的说就是一个集合是一堆男生，一个集合是一堆女生
然后一个男生或女生可能与多个人有好感度
有好感度的2个人可以成为夫妻，问你最多能组成多少对夫妻，并且不能出现脚踩多条船的情况
做法
从第一个男生开始匹配，依次遍历与他有好感度的女生，如果这个女生是单身状态就让他们成为夫妻
如果有一个男生所有有好感度的女生全部与其他人成为夫妻，那么就看看与这个女生结为夫妻的男生是谁，如果这个男生可以与其他人结成夫妻，就让他与其他人结为夫妻
https://www.acwing.com/activity/content/code/content/9372827/
