Hobo Chen

ACM-图论(TBD)

这篇博客包含了一些常见图论算法。

这里的图论特指图论中不包含 流算法 的那部分。

基础:

  • 图的存储方式(邻接矩阵, 邻接表, 边表);
  • 图的遍历(DFS, BFS);
  • 最短路问题
    • 单源最短路(Ddijkstra, SPFA)
    • 多源最短路(Floyd)
    • 差分约束(SPFA);
  • 无/有向图的欧拉路/圈;
  • 最小生成树(Kruskal, Prim);

进阶:

  • LCA问题(做法非常多);
  • 二分图最大, 最优匹配(KM);
  • 无向图的割点, 割边(Tarjan);
  • 无向图的双连通分量(Tarjan);
  • 有向图的强连通分量(Tarjan);
  • 2-SAT问题;

  • 混合图的欧拉路/圈;

  • 全局割(Stor-Wanger);
  • 生成树进阶
    • 最优比率生成树
    • 增量生成树
    • 瓶颈生成树
    • 次小生成树
    • 有向生成树(树形图);
  • 最短路进阶
    • etc

流算法通常难于建立模型,所以以后把流算法单独写;当然流算法可以高效的解决二分图问题,比如Dinic就可以在平面图做到 $EV^{\frac 1 2}$ 的复杂度。

以及LCA的做法非常多:

算法名 复杂度 备注
ST算法 O(nlog(n))预处理,O(1)查询 可在线
倍增 O(nlog(n))预处理;O(log(n))查询 可维护附加信息
Targin 预处理+查询O(n) 强制离线
树链剖分 O(n)预处理,log2(n)查询 可维护附加信息

基础

存储方式

邻接矩阵

图有$n$个点,则有一个$n \star n$的方阵$D$,$D_{ij}$表示i->j的权。

这种方式不能有重边。

邻接表

边表

最短路

单源最短路

Dijkstra和SPFA在完成 $n^2$ , $km, \quad k \in [2,n]$ 的处理之后,可以在O(1)时间内查询任意两点之间的最短距离。以及SPFA可以完成对负环的判断。

POJ3259 - Wormholes

判断存不存在负环,存在输YES。

差分约束

差分约束指一些形如 $x_j−x_i \leq b_k$ 的不等式组,其中bk已知,那么如下建图:对于每个等式建立i→j,权值为bk,另加一个超级源s,连向每个点,权值为0。以S为起点使用SPFA算法,若无负环即存在解。解为S到i的距离。

生成树

Prim

Kruskal

最优比率生成树

HDU2489

进阶

欧拉路/圈

无向图

这里把路和圈严格区分开,路特指不是圈的路。下同。

  • 保证图连通
  • 存在欧拉圈则所有点的度数均为偶数
  • 存在欧拉路则有且仅有两个点的度数为奇数

POJ1041 - John’s trip

无向图的欧拉圈,要求找到一个边字典序最小的方案。

有三个注意点:

  • 边字典序不等于深搜的时候下一个点是当前点连去的最小边编号
  • 不能使用map存储从x经过z号边到y这样一个数据结构,因为这个我TLE了3次
  • 输入比较麻烦,需要小心处理

有向图

  • 保证图连通
  • 如果要存在欧拉圈,则所有点的入度 = 出度
  • 如果要存在欧拉路,有且仅有一个点的入度比出度多1,且有且仅有一个点的出度比入度多1;其他点的入度 = 出度

POJ1386 - Play on Words

POJ-1386

混合图

混合图即是既有有向边又有无向边的图,解决混合图的欧拉路/圈问题需要借助于最大流算法。

混合图的欧拉圈

记Di=INi+OUTi,那么显然改变有向边的方向不会改变Di的奇偶性。那么当且仅当Di全为偶数的时候才存在欧拉圈。对于原图内的无向边(u,v),在网络流中建立一条u指向v,流量为1的边;代表这条边的走向只可改变一次。后对于每个Di,如果Di<0,则在网络流中建立一条i指向t,流量为di2的边;如果di>0,则在网络流中建立一条S指向i,流量为−Di2的边。

混合图的欧拉路

Di中一定有且仅有两个是奇数,设下标分别为x, y那么建立一条x指向y的虚边即可(y指向x亦可)。

POJ - 1637 Sightseeing tour

给一个混合图,询问是否存在欧拉圈。

LCA

如上文所说,LCA做法非常多。

POJ1986 - Distance Queries

比较简单的LCA问题,可以使用LCA-RMQ或者Tarjan来做。

POJ1986 - LCA-RMQ

无向图的割点割边

两遍DFS即可;使用两个数组dfn和low来分别记录dfs访问该点的编号以及这个点所能连到的编号最小的祖先。

有两种情况可以使点成为割点:

  • 该点为DFS树的根且儿子树大于1
  • 该点的某个儿子的子孙的low大于等于等于该点的DFS序

成为割边只有一种可能: (u -> v)是树边且low[v] > dfn[u]。

hiho-1183给出一个无向图,求割点、割边。

hiho-1183

连通分量

无向图的双连通分量

如果任意两点至少存在两条点不重复的路径,则称为点-双连通;等价于任意两条边都在一个简单环内;等价于无割点。

类似,如果任意两点至少存在两条边不重复路径,则称为边-双连通;等价于任意一条边都在简单环内,等价于无割边。

点-双连通分量即为图中点双连通的极大子图:

  • 不同的点-双连通分量最多只有一个公共点;并且一定是割点
  • 任意割点一定是至少两个不同的点-双连通分量的公共点
  • 可以在DFS中维护一个栈来线性地找出点-双连通分量

边-双连通分量即为图中边双连通的极大子图:

  • 除了割边,每条边都属于一个边-双连通分量
  • 删去割边后,图的连通分量数目等于边-双连通分量数目
  • 可以使用两遍DFS来找出边-双连通分量,第二遍DFS不经过割边即可

hiho-1190给每条边编号1-N,求出点-双连通分量后,询问每条边所在的点-双连通分量中边的最小编号。

hiho-1190

hiho-1184给出一个无向图,求出边-双连通分量后,询问每个点所在的边-双连通分量中编号最小的点。

hiho-1184

有向图的强连通分量

做法类似于无向图的割点,在计算lowlink的数组过程中完成SCC的计算。

hiho-1185 给出N个点,M条有向边,每个点有点权,要求从某个点出发的最大点权和。SCC缩点之后DAG_DP找最长路。

hiho-1185

2-SAT 问题

即给出若干个双变元的合取范式,询问是否存在一个使主合取范式为真的变元取值。

有一个简单的结论A∨B⇔(¬A→B)∧(¬B→A)。

依据上述结论建边,之后对图求SCC,如果有任意的A,¬A在同一个强连通分量中,则无解。

每个变元最多出现在两个SCC中,对SCC进行拓扑排序。如果¬A所在的SCC拓扑序在A之前,那么A = True。

如果变元出现在少于等于一个SCC中,则其取值为任意。

UVALive - 3713

给出一个2-SAT图,输出任意合法方案。

两个注意点:

  • 在原图建SCC图的时候需要去掉重边
  • 这道题中的平均年龄直接用long long整除人数进行比较会WA

HDU4115 - Eliminate the Conflict

这道题是个比较麻烦的2-SAT问题,把每一局选择平/赢看成0/1建图。