NOIP的图论的问题

来源:学生作业帮助网 编辑:作业帮 时间:2024/04/29 09:36:15
NOIP的图论的问题

NOIP的图论的问题
NOIP的图论的问题

NOIP的图论的问题
【图论】
图的表示:邻接矩阵,邻接表,边表
单源最短路:dijkstra(O(n2)),bellman(spfa优化,O(km))
传递闭包和floyd
最小生成树算法:prim(O(n2)),kruskal(O(m log m))
拓扑排序(O(m))
欧拉路(边一次)
汉密尔顿回路(点一次)
强连通分量
匹配算法(最大匹配,最小点覆盖,最小路径覆盖,最大独立集)
网络流算法(最大流dinic,最小费用流spfa)
差分约束系统