图论总结

Artanisax · 2019-10-20 12:08:29 · 个人记录

退役文#1

图论总结（前NOIP知识）

（注：没有板子，以例题为主，可能掺杂部分已学省选内容）

普通图

• 最短路

  1. 单源

  例1

  题意： 求1号点到N号点的最短路。

  ~~哇，单源最短路板子题！然而 dijkstra TLE 当场去世……~~ **问：** 它给的$ w∈{1,2}$有啥子用哦？ **答：** 拆w=2的边为两条w=1的边，然后bfs。$O(n+m)

  例2

  题意： 求1到N的最短路，最短路的定义为路径上最大的K条边边权和。

  **问：** 如何贪心松弛而不是压状态暴力搜？ **答：** 枚举第k大边权w，将边权减去w（最小到0）, $ans=min\left\{dis[n]+w* k\right\} $。（注：当答案路径边数<k时，$ans=dis[n]$）。$O(k* nlog(n+m))

  例3

  题意： 丛林中共有n棵果树，每一棵果树上都有数量不等的果实。果树之间有单向边连接，不构成环。你提着一个篮子从编号为1的果树出发，选择一条路径走到编号为n的果树。每当你走到一棵果树的时候，你都会将这棵果树的所有果实采摘下来，放入篮子中，这个过程不花费时间。你在路上行走的时候，每走1分钟，你都会吃掉一个果实除非篮子空了。

  求出篮子至少要能够承担多少个果实，才能够选择一条路径（途中不扔掉果实）。

  n<=1000,m<=5000

  问： 这又有点权又有边权的，怎么我想到的又是压状态爆搜？

  答： 求的不是最大值最小吗？二分答案呀！松弛时如发现max(0,mn[u]-w[i])+val[v]>mid 就不管它了，看能否到终点。O(logn* nlog(n+m))

  例3: K短路

  采用 A* 进行bfs，估值函数为反向最短路。

  2. 多源

  一说多源那就是Floyed算法了，但它肯定不会只考个板子，经常会结合矩阵之类的操作或考察对Floyed的理解。

  例1

  题意： 给出一个带权有向图的邻接矩阵，两个操作：

  操作1：删除一条边

  操作2：询问任意两点最短路

  **理解：**Floyed本质是DP，本题倒序处理将删边改成连边，再用新连的边$n^2$去更新dis，就像截了一小部分Floyed的过程一样。$O(n^3+m)

  例2

  题意： 给定起点终点和T条跑道，求经过N条边的最短路。

  T<=100,N<=1e6

  矩阵：用矩阵表示出图的初态，然后用矩阵快速幂求出最终图的状态，但得将矩阵乘法的 + 改成 取min。O(logn*T^3)

  3. 差分约束

  这个就不用例题了，式子列对了跑SPFA就好了，但注意条件特殊时可以用拓扑排序。

  4. 分层图

  例1

  题意： 总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。一条路径越快，或者费用越低，该路径就越好。如果没有一条路径比某路径更好，则该路径被称为最小路径。

  求最小路径的总数。

  1≤n≤100,0≤m≤300,0≤c,t≤100

  将双边权中的一种作为状态分层，最后统计答案。

  NOIP似乎挺喜欢考的,就列几道原题吧。

  例2 「NOIP2017提高组」 逛公园

  先求出最短路，将所选路径比最短路多出多少作为状态分层，然后记忆化搜索。

  例3 「NOIP2009提高组」 最优贸易

  由于贸易只进行一次，可以分三层，第一层决定在哪里买入，第二层决定在哪卖出，第三层看能否走到终点。

• 拓扑排序

  例 「NOIP2003提高组」 神经网络

  emmm现代科技文阅读，看出分层与入度有关后拓扑排序即可，但注意输入层的阈值无用（题面描述十分显眼）。

• 连通性

  1.tarjan

  有向图：强连通分量（SCC）

  无向图：（点）双连通分量（SCC）、边双连通分量（EBC）

  通用：割点、割边（桥）

  2.连通块

  并查集维护连通关系。

  常见问题处理方法：

  删边 -> 倒序处理转成连边合并

  又加又删的 -> 线段树分治 + 可撤并查集（会 LCT 的出门左拐）

• 思维/优化建图

  1. 数学

  如取模等运算在一定限度时可以看作为连边。

  2. 线段树优化

  建立线段树用节点表示区间，注意树上的点需要额外连边。

  3. 其它

  虚点、虚边、拆点等常用技巧就不多说了。

树

• 生成树

  1. 最小生成树

  例

  题意 B国有n个城市，编号依次为1到n。这些城市之间通过m条双向道路连接，其中第i条道路连接着ui,vi这两个城市。任意两个城市之间可能有多条道路，也有可能从1号点出发不能到达所有城市。

  对于第 i个城市，占领这座城市则需要在这里聚集 ai个特种兵，而在这里空降1个特种兵的代价为bi。对于第i条道路，占领这条道路需要在道路两端点的城市累计聚集ci个特种兵。

  A国的目标是占领B国所有的城市（不需要占领所有道路），对于占领过的城市和道路，A国不需要派兵一直驻守。请写一个程序，帮助A国以最小的总代价占领B国所有的城市

  思路：无需驻守->连通块信息、合并连通块->最小生成树

  2. 最短路生成树

  例

  题意： 一个n个点m条边构成的无向带权图。由一些黑点与白点构成

  树现在每个白点都要与他距离最近的黑点通过最短路连接（如果有很多个，可以选取其中任意一个），我们想要使得花费的代价最小。请问这个最小代价是多少？

  注意：最后选出的边保证每个白点到黑点的距离任然是最短距离。

  解：建立虚点，连接所有黑点，跑一遍最短路，最后生成一颗建立在最短路图上的最小生成树。

• 基环树

  枚举断边作树处理。

网络

（只学过dinic的我瑟瑟发抖）

dinic注意当前弧及阻塞优化以达到玄学复杂度。

• 最大流

  找准源点、汇点、管道、容量（必要时使用建虚点、连虚边、拆点等建图技巧），然后跑就是了。

• 最小割

  1.最大权闭合图

  例1「网络流24题」太空飞行计划SPJ

  割源表示不选，隔汇表示选入

  例2 「CEOI2008」 order

  将两集合间的边由INF变为租价（本题理解为租用仅对该工作生效）

2-SAT