图论

· · 个人记录

最短路

几种常用的求最短路方式

  1. Floyd$ $O(n^{3}) f[i][j]=min(f[i][j],f[i][k]+f[k][j]) 还可以倍增求定长步数是否可达 矩阵求 定长路径统计，定长最短路，限长路径计数/最短路等 见[oi-wiki](https://oi-wiki.org/math/linear-algebra/matrix/#%E5%AE%9A%E9%95%BF%E8%B7%AF%E5%BE%84%E7%BB%9F%E8%AE%A1)
  2. 用队列优化的spfa慎用
  3. Dijkstra

    重要知识点：最短路树

    例题USACO09JAN Safe Travel G

    题目要求出在不经过原来1节点到i节点最短路上最后一条边的前提下，1节点到 i 节点的最短路

    求出最短路径树，由于1到每个点的最短路唯一，最短路径树也唯一

    易证：新的路肯定只会经过一条非树边 因为另一条肯定可以被树上一条路径代替
    那么答案就很明显了:ans_i=min(dis[u]+dis[v]+w_{u,v}-dis[i]))

    将所有非树边按照答案排一遍序,更新能更新的点，并查集优化即可

题：SDOI2009 Elaxia的路线 JOI2018 Commuter Pass

  1. 同余最短路

    通过同余构造某些状态，状态之间的关系类似于两点之间的带权有向边。

    那么可以以此建图，将某些问题转化为最短路问题，再使用具有优秀时间复杂度的算法求解。

题：墨墨的等式 跳楼机

最小生成树

  1. Kruskal 算法

    重点讲Kruskal重构树的性质：

    • 性质1

    • 性质2 任意一个结点到根的路径上的结点点权递增

    • 性质3 从一个结点u出发,能通过的边的边权阈值为c。

题：货车运输 归程

  1. 次小生成树

枚举非树边(u,v),在树上找到一条最大边替换，更新答案即可

严格再维护次小值即可

题：严格次小生成树

二分图

  1. 染色法判断二分图

  2. 扩展域并查集判断二分图

  3. 匈牙利算法求最大匹配

    二分图的一些性质

    1.二分图的最小点覆盖=二分图的最大匹配

    2.最大独立集=n-最大匹配

    3.有向无环图的最小路径点覆盖=n-拆点二分图的最大匹配
    拆点二分图：对于一条有向边(u,v)，将u向v+n连一条边

    4.有向无环图的最小路径可重点覆盖 

    先跑一遍floyd 求出每个点能到的所有点   
再跑一遍最小点覆盖即可

连通分量

  1. 强连通分量
    缩点后是一个有向无环图

  2. 点双连通分量
    一个割点至少属于两个点双中

  3. 边双连通分量
    缩点后是一棵树

板子：边双连通分量 点双连通分量

连通分量的套路就是 缩点后跑dp,难度主要还是在dp上

题：NOIP2022建造军营 HNOI2012矿场搭建

优化建图

  1. 线段树优化建图
    板子：Legacy

  2. 建超级源点
    题：PA2012Tax