图论

Published: by Creative Commons Licence

  • Tags:

生成树

一个无向连通图的生成树是指该图的一个连通无环子图。而最小生成树就是所有生成树中总边权最小的。

因为之后的分析要用到最小生成树的一些性质,因此这里详细介绍下。

割点和割边

定义1:给定无向图,如果删除某个顶点$v$后,导致图中的连通分量增多,那么称这个点是割点。

定义2:给定无向图,如果删除某个边后,导致图中的连通分量增多,那么称这个边是割边。

割边的求法非常简单,利用tarjan算法进行缩点后得到一棵树,这棵树中的所有边都是割边。这也意味着割边最多存在$V-1$条。

割点的求法类似,先求出任意一株生成树。如果根下面挂了一颗以上子树,那么根顶点一定是割点。对于其余顶点$v$,如果$v$不能访问到比父亲顶点dfn序号更小的顶点,那么就意味着父顶点对于$v$是一个割点。

DFS生成树

一篇不错的博客

对于一个连通图图,我们可以通过DFS求出其中一个生成树,这样的生成树我们称为DFS生成树。显然只有一部分边被加入到了生成树中,加入的边我们称为生成边,其余边称为备用边(back-edge)。

DFS生成树特性:

  • 所有备用边都连接某个祖先和其后代。
  • 每条备用边的加入都会构成一个简单环。
  • 对于任意一条生成边$(u,v)$,其中$u$是$v$的父亲,$(u,v)$是割边当且仅当不存在连接$u$的祖先和$v$的后代的后备边。
  • 连通分量是强连通分量当且仅当其中不存在割边。

讨论几个DFS生成树的应用:

题目1:给定一副连通无向图,不存在自环和重边,要求将每条边转换为有向边且要求转换完成后,所有顶点对之间都存在至少一条路径。判断是否存在方案,如果存在,则输出任意一种可行方案。

由于转有向图后强连通,因此有向图中不存在割边,那么原来无向图也一定不存在割边,即原图必须是强连通的。这是必要条件。

先生成无向图的一个DFS生成树,之后我们将所有的从生成边的方向设置为祖先指向后代,而将所有备用边的方向设置为后代指向祖先。

下面我们保证上面的图是强连通的。很显然从根顶点$r$到其余顶点都存在路径,现在考虑任意顶点$v$,假设其父亲为$u$,且其父亲到根存在一条路径,那么由于$(u,v)$不是割边,因此存在一条跨越$(u,v)$的备用边$(s,t)$,其中$s$是$t$的后代。我们可以沿着路径$v..t,s..u..r$从$v$抵达$r$。利用归纳法可以证明所有顶点都可以抵达根,因此有向图是强连通的。

题目2:给定一副无向图,不存在自环和重边,且保证每个顶点的度数大于等于$k$。现在要求找到任意一个长度大于等于$k+1$的简单环(无重复顶点)。

首先生成DFS树,考虑DFS树的任意叶子顶点,与其直接相邻的生成边的数目为$1$,因此至少还有$k-1$条后备边。由于每条后备边连接不同的祖先顶点(不是父亲顶点),因此有一个祖先顶点至少距离当前顶点$k$,于是乎加上这条后备边就构成了一个长度大于等于$k+1$的简单环。

题目3:给定一副$n$个顶点的无向图,不存在自环和重边。要求要么找出一个大小为$\lceil \sqrt{n} \rceil$的独立集,要么找到一个长度至少为$\lceil \sqrt{n} \rceil$的简单环。

我们可以利用贪心算法来找独立集,每次选择度数最小的顶点,选择它并删除所有与其关联的顶点以及它,这个过程直到剩余所有顶点度数都大于等于$\lceil \sqrt{n}\rceil-1$或者没有顶点了才停止。在这个过程,由于找到的度数最小的顶点度数小于$\lceil \sqrt{n}\rceil-1$,因此每次选择最多使得$\lceil \sqrt{n}\rceil-1$个顶点不可用。如果所有顶点都被消除了,那么我们至少选择了$\lceil \sqrt{n}\rceil$轮,即我们得到了一个满足条件的独立集。否则,剩余的顶点的度数都至少为$\lceil \sqrt{n}\rceil-1$,而这保证我们一定能找到一个长度至少为$\lceil \sqrt{n}\rceil$的简单环。

提供一道题目

题目4:给定一副$n$个顶点$m$条边的简单无向连通图(无自环重边),保证每个顶点度数都至少为$3$。给定某个数$k$,现在要求找到找到一条长度为$\lceil \frac{n}{k}\rceil$的简单路径(无重复顶点);或者找到$k$条长度至少为$3$,且长度不能被$3$整除的环,且每个环都至少有一个独属于自己的顶点。

很显然对于每个叶子顶点,其至少有两条备用边连向不同的祖先,而这会构成三个环,其中至少一个环不能被$3$整除。且每个环都包含这个叶子顶点,我们可以将叶子顶点作为独属的顶点。

如果有$k$个叶子顶点,那么我们就直接求出解了。否则我们记$d_i$为第$i$个叶子顶点的深度,且$c_i$为叶子数,那么一定有$\sum_{i=1}^cd_i\geq n$,因为从每个叶子向上走可以覆盖所有的顶点。之后利用鸽巢原理可以直接得出至少有一个叶子$i$深度满足$d_i\geq \lceil\frac{n}{c}\rceil \geq \lceil\frac{n}{k}\rceil$。这样我们就找到了路径了。

prim和kruskal

最小生成树的求法不外乎两种,prim和kruskal。两个都是贪心算法,正确性基于最小生成树类似的性质。

随意取一个顶点u,记所有与u关联的最小权边为$e=(u,v)$,其中$u\neq v$。现在我们证明e一定属于一株最小生成树,用反证法。假设最小生成树T中不包含e。我们知道e是与u关联的最小边,因此可以将e加入到T中,这样就会出现一个包含点u的环。删除环上与u相连的另外一条边e',得到了一株新的树T',而T'的总权不可能大于T(加入e删除了e',e的权重小于等于e'),因此weight(T')<=weight(T)。这样我们就得到了包含e的一株最小生成树。

由这个观察我们可以推出贪心的流程。

  1. 创建一个空集T。

  2. 任意取一个顶点u,找到与该顶点u相关联的最小权重边e=(u,v),满足$u\neq v$,从点集V中删除u、v,并将e加入到空集T中,之后合并顶点u、v,将合并后的顶点加入到V中。
  3. 如果V中只剩一个顶点了,那么就结束,此时T就是最小生成树。否则回到步骤2。

上面这个流程就是prim算法。由于并不限制步骤2的u的选择,因此你可以总是选择顶点1以及包含顶点1的合并顶点,这样整个流程就完全等价于dijkstra算法了,用最小堆优化后得到的时间复杂度为$O(\min((V+E)\log_2V, V^2))$。

prim算法是通过点去找边,也可以通过边去找点,下面的算法就是如此:

  1. 创建一个空集T。
  2. 从边集E中弹出权重最小的边e=(u,v),如果在生成树T中u、v不处于相同连通块,就将e加入T中,否则忽略e。
  3. 如果E为空集,那么就结束,此时T就是最小生成树。否则回到步骤2。

上面这个流程就是kruskal算法,我们可以提前对E进行排序,并用路径压缩并查集维护连通块,这样时间复杂度为$O(E+E\log_2E)$。

最小瓶颈路

一条路径中,权重最大的边称为路的瓶颈,而从起点到终点的所有路径中瓶颈最小的路径称为最小瓶颈路。

对于两个不同的顶点i,j,记$f_{ij}(x)$表示只保留图中权重不超过x的边的前提下,顶点i与j是否连通(连通为1,不连通为false)。很显然这样的函数$f_{ij}$一定是非严格递增函数。假设i、j之间的最小瓶颈路的瓶颈权重为t,那么$t$一定是$f_{ij}$最小的能令其返回1的入参。

因此我们可以先对边集按照权重从小到大进行排序,之后按序将边的两个端点所在连通块合并为一个连通块。这个过程持续直到i和j处于相同的连通块中。

这个流程实际上和kruskal是如同的,因此我们可以相信最小生成树中的任意两个端点i、j之间的唯一路径就是图上的最小瓶颈路。

求所有最小生成树的并集

给定一张无向连通图,求其所有最小生成树的并集。

有两种方法。

第一种方法,就是先任意构建一个最小生成树,显然最小生成树中的所有边都要被包含进去。考虑任意未被包含进最小生成树的边$e=(a,b)$,其连通两个顶点,考虑最小生成树中从a到b的唯一路径上权重最大的边$e'$,由于最小生成树具有最小瓶颈路的性质,因此$e'$的权重不可能大于$e$。如果$e'$的权重恰好等于$e$,那么我们可以从最小生成树中删除边$e'$并加入$e$来获取一颗新的最小生成树。

上面的总的时间复杂度为$O((n+m)\log_2n)$,路径操作可以用LCT实现。

第二种方法是,考虑kruskal算法,我们将边集按照边的权重进行分组,第i组就是所有权重为i的边组成的集合。注意到我们可以通过变换同组边之间的处理顺序得到所有的最小生成树。我们可以证明不管如何打乱同一组边的处理顺序,在处理完第i组的边后,所有的连通关系都是相同的,即在一种顺序下两个顶点是连通的,那么在另外一种处理顺序下亦然。这个可以利用归纳法进行证明,假设处理完前i-1类边后连通关系相同。那么考虑以任意顺序处理第i类边,如果第i组边中所有边最后都被加入最小生成树,那么连通关系肯定相同。如果不是所有边被加入,那么考虑任意一个未被加入的边$(a,b)$,那么我们可以断定a和b一定连通(否则我们可以将$(a,b)$纳入最小生成树中)。因此当我们处理完前i类边后,对于任意前i类边$(u,v)$,$(u,v)$一定是连通的。

而一条边是否有机会组成最小生成树,假设边的权重为k,那么我们只要观察,在处理完前$k-1$类边后,这条边的两个端点是否连通即可。第二种方法的时间复杂度也是$O((n+m)\log_2n)$,但是这边不需要用到LCT,只需要用到并查集即可。

求最小生成树的数目

最小生成树的数目可以通过kruskal算法求出。在求所有最小生成树的并集这一节中,已经说过了所有kruskal算法流程中,可以通过变换边的处理顺序得到所有的最小生成树。事实上,对于固定的图,要得到最小生成树,其中所有权重为i的边选取的数量也是固定的(和边的处理顺序无关)。假设最小生成树中权重为$i$的边共选择了$c_i$个,那么我们在处理第$i$类边的时候,可以暴力枚举选取$c_i$条边的,情况,去除其中成环的情况。不同权重的边可以独立处理。

最小生成树的一些题目

题目1:给定$n$个顶点$m$条边构成的无向连通图,第$i$个顶点的权值为$w(i)$。要求找到一组边,构成生成树,且要求$\sum_{v}deg(v)w(i)$最大

我们发现加入一条边$(u,v)$,会导致结果增大$w(u)+w(v)$。我们可以将$w(u)+w(v)$作为边$(u,v)$的权值,用最小生成树算法找到最大生成树即可。

Euler Tour Tree

Euler Tour Tree也是动态树,支持$O(\log_2n)$的换根,加边,删边操作。类似于Link-Cut-Tree,但是底层原理是将树表示为DFS序,并将DFS序放到平衡树上去维护。

要了解更多,可以去阅读斯坦福大学的课件,地址如下:

http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/05/Slides05.pdf

Euler Tour Tree和Link Cut Tree的区别在于,后者是以Splay森林保存信息,每个森林中的树都代表一条树上的路径,因此Link Cut Tree非常适合用于处理路径问题。而前者是以一株平衡树进行维护的,因此可以很好的利用树的一些性质,比如处理子树问题。

连通性检测

对于一个含有n个顶点的无向图,一开始边集为空。你需要处理m个请求,请求内容为下面三类:

  1. 增加一条边
  2. 删除一条边
  3. 判断两个顶点是否处于相同相同的连通块中

离线线段树做法

现在我们换个角度来理解问题,有m个时间点,每个时间点,每个请求都会修改某个时间区间的状态。最后要求在所有请求完成后,每个时间点的状态。

这涉及到了区间修改和单点查询,妥妥的就是线段树啊。我们可以把每个请求看成一个事件,事件从某个时间点$L$起到某个时间点$R$结束。我们可以用线段树来存储事件,但是特殊的是,我们不下推时间,即如果有一个线段树顶点代表的区间被某个时间完整覆盖,那么我们将这个事件绑定到这个顶点上,而不继续下推。

很容易证明每次请求最多会修改$\log_2m$个顶点。而最后查询的时候我们在进入顶点的时间执行所有的事件(合并连通块),而在离开顶点的时候撤销所有事件(分裂连通块),由于连通和分裂是一个栈式操作,因此我们可以用不带路径压缩的并查集来维护连通块。由于每个事件只会被处理两次(执行和撤销),而总共有$m\log_2m$个事件,每次合并分裂的时间复杂度均为$\log_2n$,因此总的时间复杂度为$O(m\log_2n\log_2m)$,空间复杂度为$O(m\log_2m+n)$。

特殊情况做法

如果存在某个特殊的数$x$,满足前$x$个请求都是加边,而后$m-x$个请求都是删边操作,那么我们可以以线性时间复杂度计算出结果。

具体做法如下。容易发现没有删除操作的情况下,只需要用并查集就可以维护所有连通块,因此前$x$个请求一定能在线性时间复杂度内完成。现在考虑后$m-x$个删除操作。假如删除操作完成后,我们进行回退,会发现我们只需要执行$m-x$个增加操作即可。因此结果还是$O(m-x)$。

总的时间复杂度和空间复杂度都是线性的。

离线LCT做法

如果题目可以允许我们离线,我们可以用Link-Cut-Tree轻松解决这个问题。按序处理请求:

  1. 假设要加的边为e=(u,v),我们先检查后面第一个删除边e的类型三请求出现的序号,记作t,将e的寿命设为t。假如此时u和v不连通,那么就直接插入e,用e将u和v连通。否则,我们判断u和v所在路径中寿命最短的边z,判断z的寿命是否小于e的寿命,如果小于,删除z加入e,否则忽略e。
  2. 不处理。
  3. 假设要处理的顶点对为u、v。先判断u、v是否连通,不连通,则必定不连通。如果连通,就判断u、v之间路径上寿命最短的顶点z,如果z的寿命小于当前请求的序号,则不连通,否则连通。

利用离线做法,我们每次请求都变成了常数次LCT操作,总的时间复杂度为$O((n+m)\log_2n)$。

题目1:给定一个包含$n$个顶点的,开始的时候没有边。之后$m$个操作,每个操作指定一条边,如果边不存在,则插入,否则删除。要求在每个操作完成后,判断当前图是否是二分图。其中$n,m\leq 2\times 10^5$

题目

首先我们可以转换一下问题,将问题改写为,有若干条边,边有出现时间和删除时间,从时间$1$到时间$m$,问图是否是二分图。

一道比较有趣的题目。总所周知,一个图是二分图,当且仅当它没有奇环。

因此我们考虑插入一条边和删除一条边后快速判断图中是否存在奇环。维护一个边$T$,考虑现在处理第$i$个请求。假设要求插入一条边,如果没有形成环,那么图的奇偶性是不会改变的。否则形成环,分两种情况讨论:

  • 形成的是偶环。这时候我们选择环上最早被删除的边删除。
  • 形成的是奇环。我们记录环上最所有边的删除时间的最小值$t$,将$T$更新为$\max(t, T)$。同时删除环上最早被删除的边。

利用LCT以及离线化,上面的算法可以在$O((n+m)\log_2n)$时间复杂度内解决。下面我们证明算法的正确性。

在没有形成环的情况下,我们确实插入了一条边$(u,v)$,并且没有形成额外的环,因此这一步是正确的。考虑形成偶环的情况,假设被删除的边为$(a,b)$,我们可以保证,如果之后在原图中出现了包含边$(a,b)$的环,那么在我们维护的生成树中会出现一个包含$(u,v)$的与其奇偶性相同的环。最后考虑奇环的情况,由于出现了奇环,且奇环上最早被删除的边的删除时间为$t$,那么对于之后到第$t$个请求前,图都是包含奇环的,因此所有后面的边,我们都可以将其出现时间推迟到$t$或之后(因为这个时间新插入的边不能影响图是否是二分图)。基于这个假设会发现,我们的图中始终不会出现奇环,因此我们只需要维护一颗生成树而已。

在线做法

如果问题强制要求我们在线,那么就需要使用euler tour tree来解决问题。

首先我们将边分成$L=\log_2n$层。对于边e,记Level(e)表示e所在图的层级,边的层级只降不升。同时建立L个图$G_i$,其中$G_i$包含所有n个顶点和所有层级不超过i的边,我们维护它的最小生成树$F_i$,每个边的权重就是它们所在的级别。我们需要维护两个不变的性质:

  1. $G_i$中的连通块大小不会超过$2^i$
  2. $F_i=F_L \cap G_i$。

维护一个集合E用来保存所有的加入后没有删除的边的信息。接下来按先后顺序处理所有请求:

  1. 设新增的边为e=(u,v),将e加入E,将Level(e)设为L。之后检查$F_L$中u、v是否连通,如果不连通就向$F_L$插入e,否则忽略。

  2. 设删除的边为e=(u,v),先从集合E中删除e。首先如果e不出现在$F_L$中,那么流程直接结束,因为不会影响到连通性。下面考虑e出现在$F_L$中的情况:

    • for i = Level(e) -> L:

      • 从$F_i$中删除e
        • 删除了e并不能保证u、v就不连通了,因为可能存在替换边,我们可以保证假如替换边存在,那么替换边的级别至少是Level(e),(由最小生成树性质得到)
    • for i = Level(e) -> L:

      • 由于删除了边e,我们将原先u、v所在连通块切分为了两部分,分别记作$B_u$和$B_v$。这里加色和$B_u$的大小不超过$B_v$,考虑到$|B_u|+|B_v|\leq 2^i$,因此$|B_u| \leq 2^{i-1}$,因此我们可以将$B_u$中的全部级别为i的边下推到级别i-1中去
      • 下推$B_u$中的全部级别为i的边到级别i-1中去。
      • for (x, y) in E where Level((x,y))=i and x in $B_u$:
        • if x、y在$F_L$中处于相同的连通块中:
          • 将(u,v)的级别减少1
        • else:
          • 将$(u,v)$加入到$F_i,F_{i+1},\ldots, F_L$中去。并结束过程。
  3. 假设要查询的顶点对位u,v,只需要判断在$F_L$中u、v是否在相同连通块中即可。

对于操作1,时间复杂度为$O(\log_2n)$。对于操作2,时间复杂度为$O((\log_2n)^2)$。由于每条边被下放最多$L$次,因此这部分的时间复杂度为$O(m(\log_2n)^2)$。总的时间复杂度为$O(m(\log_2n)^2)$。

最短路算法

一些记号:

  • $G$: 图
  • $V$: 顶点集合(在公式中表示顶点数目)
  • $E$: 边集(在公式中表示边数目)
  • $(u,v)$: 从$u$到$v$的边
  • $W(u,v)$: 边$(u,v)$的权重
  • $D(u)$: 从源点到$u$的最短距离
  • $L(u)$: 从源点到$u$的最短路径的拥有的边数(长度)

BFS算法

BFS算法适用于这样一类图,所有的边的权重恰好都是1。BFS算法的时间复杂度为$O(V+E)$。

BFS算法非常简单,我们需要维护一个先进先出的队列,一开始将除了源点外所有顶点的距离设为无穷,而将源点的距离设为0。之后我们将源点加入到队列中,重复下面过程直到队列为空:

  1. 弹出队列头部顶点,记作$u$。
  2. 遍历$u$的所有出边$(u,v)$,如果$D(v)>D(u)+1$,那么就令$D(v)=D(u)+1$,并且将$v$加入到队列尾部。

BFS算法实际上会先找到最短路径为0的所有顶点,之后是为1的,之后为2的,如是循环。很显然,由于在加入$v$的时候,所有最短距离小于$D(u)$的顶点都已经被处理了,因此可以保证之后$v$的距离都不会再变化,因此每个顶点恰好被入队以及处理一次,总的时间复杂度为$O(V+E)$。

01权重BFS算法

BFS算法除了可以解决所有边权为1的图的最短路,还能解决所有边权为0或1的图的最短路问题。

非常简单,BFS的原理是一个简化版本的Dijkstra算法,我们用维护一个距离递增的队列来存储顶点。而实际上维护这样一个队列,是可以允许边为0的。考虑现在处理的队列前端元素为$v$,那么很显然弹出$v$后,队列中的所有元素距离都不小于$D(v)$。这样假如存在一条$0$权重边$(v,u)$,那么我们得到了$u$的距离也是为$D(v)$,这意味着将$u$加入到队列前端也不会影响队列中顶点距离递增的性质。因此我们这也就可以直接支持0或1边权的图了。

单源最短路算法:Dijkstra算法

Dijkstra算法要求图中的所有边权非负,它的时间复杂度为$O(\min(V^2+E,(V+E)\log_2V))$。

Dijkstra算法基于贪心算法,同样我们需要一开始将除了源点外所有顶点的距离设为无穷,而将源点的距离设为0。之后我们重复下面操作直到所有顶点都被处理过了:

  1. 找到所有未处理的顶点中最短距离最小的那个顶点$u$。
  2. 将$u$标记为处理过
  3. 遍历所有$u$的出边$(u,v)$,如果$D(v)>D(u)+W(u,v)$,那么就令$D(v)=D(u)+W(u,v)$。

很显然上面的算法时间复杂度为$O(V^2+E)$。如果我们采用小根堆来存储顶点,那么时间复杂度就变成了$O(V+E)\log_2V)$。

下面证明一下Dijkstra算法的正确性。我们证明两点:

  1. 被处理过的顶点$x$按照处理顺序,其处理时标记的距离$tag(x)$非严格递增。
  2. 每个顶点$x$被处理的时候,其标记的距离$tag(x)$就是真正的最短距离$D(x)$。

第一点证明可以通过归纳法,很显然第一个处理的顶点是起点,其标记的距离为$0$,就是最短距离。之后考虑第一个被处理的顶点$v$,满足$tag(v)<tag(u)$,其中$u$在$v$之前被处理。那么由于$v$是第一个这样的顶点,因此$v$的前驱顶点$p$一定满足$tag(p)\leq tag(v)<tag(u)$,即$p$应该在$u$之前处理。而此时在$u$处理之前就有$tag(u)>tag(v)$了,因此$u$不可能在$v$之前处理,这里出现矛盾,因此第一点得到证明。

考虑第二点,同样通过归纳法进行证明。第一个被处理的点为起点$s$,因此$tag(s)=D(s)=0$。假设从$s$到$v$的最短路中除了$v$外其余顶点都满足标记距离等于最短距离。如果有$tag(v)>D(v)$,那么说明$v$一定在其前驱$p$处理之前被处理,考虑到$tag(v)>D(v)\geq D(p)=tag(p)$,根据第一点我们知道$v$一定在$p$之后处理,这里产生矛盾,因此第二点得到证明。

Dijkstra算法实际上使用了一个非常简单的贪心算法解决了无负权边情况下的最短路问题。它实际上还有很多优化的手段,比如用配对堆可以将时间复杂度优化到$O(V\log_2V+\alpha E)$,其中$\alpha$可以视作一个非常小的常数。因此对于顶点数比较少,但是边数非常多的情况也是可以适用的。还有一种特殊情况就是距离起点最远的顶点的距离为$D$的时候,还存在一个时间复杂度为$O(V+E+D)$的变种,具体就是维护$D+1$个普通队列,之后按照编号从小到大处理每一个队列,距离为$d$的顶点则放在第$d$个队列中。

单源最短路算法:Bellman-Ford算法

BM算法允许负权边,并且可以判断图中是否有负权环,它的时间复杂度为$O(V(V+E))$。

BF引入了松弛的概念,非常简单就是选一组顶点,遍历它们的出边,然后尝试优化入点的最短距离,比如说考虑顶点$u$,如果存在出$(u,v)$且$D(v)>D(u)+W(u,v)$,那么就将$D(u)$修改为$D(u)+W(u,v)$。

由于有负权边存在,因此Dijkstra采用的贪心策略是不能保证正确性的。但是我们可以发现在图上选择所有顶点跑一次松弛后尽管大部分顶点的最短距离是错误(大于真实的最短距离)的,但是对于$L(u)=1$的顶点$u$,它的最短距离是此时正确的。同理,当我们跑$k$次BFS后,所有满足$L(u)\leq k$的顶点$u$的最短距离都是正确的。

因此当图中不存在负权环的时候,由于对于任意顶点$u$满足$L(u)<V$,因此我们只需要在原图上选择所有顶点跑最多$V-1$次松弛即可。

当图中存在负权环的时候,那么我们在跑完$V$次BFS后如果有顶点的$L(u,v)$被标记为$V$,那么就一定存在了负权环。

无论是否存在负权环,时间复杂度的上界都是$O(V(V+E))$。

单源最短路算法:Spfa算法

Spfa的全称是Shortest path faster algorithm,我们可以将其理解为BF算法的优化版本(但是并没有优化时间复杂度的上界)。

考虑BF算法,我们发现如果某个顶点在上一次的BFS的最短距离没有变动,那么在下一次的BFS的时候就没必要将其作为源点加入。

Spfa算法的优化就是这么简单,其具体实现就是维护一个先进先出的队列,如果一个顶点的最短距离被修改了就入队。循环直到队列为空,或者某个顶点$u$的$L(u)\geq V$,前者无负环,后者表示出现了负环。

在不存在负环的时候Spfa一般会比BF算法快一点,但是有负环的时候两者相差不大。

全源最短路算法:Floyd-Warshall

FW算法可以用于计算图中每个点对的最短距离,FW允许负权边,但是不允许存在负权环。

我们用动态规划来计算所有点对的最短距离。由于s与t的最短距离必定会对应至少一条最短路径s..t,而s..t中除了两个端点外序号最大的点记为M(s..t),称为路径的最大点。利用函数M,我们可以将图中所有路径分类为n种,第i类路径,其最大点为i。

FW算法的原理就是按分类从小到大处理所有路径,并利用这些路径计算得到所有点对之间的最短距离。记D(i,j,k)表示所有从i到j的前k类路径中最短的路径长度。对于D(i,j,k+1),很显然i与j之间的最短路要么是前k类路,要么就是第k+1类路。如果是第k+1类路,这条路中的最大点为k+1,将路以k+1为断点分裂为两条,i..k+1,k+1..j,很显然两条路都是前k类路。因此:

之后动态规划,$O(n^3)$可以解决。

for(k = 1; k <= n; k++){
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            D[i][j] = min(D[i][j], D[i][k]] + D[k][j]);
        }
    }
}

全源最短路算法:Johnson

这个算法允许图中出现负权边,但是不允许图中出现负权环。它的时间复杂度为$O(\min(VE\log_2V, V^3))$,在图比较稀疏的时候会优于Floyd算法。

我们知道在没有负权边的时候,可以将每个顶点作为源点跑一次Dijkstra算法,这样的时间复杂度为$O(\min(VE\log_2V, V^3))$,那么在有负权的边的时候,能不能也用Dijkstra算法呢?Johnson算法就解决了这个问题。

首先我们向图中加入一个新的顶点,并从新的顶点到所有其它顶点建立一条权重为$0$的有向边,之后我们计算以新顶点作为源点的单源最短路(由于图中有负权边,所以使用BF算法)。

现在我们得到了每个顶点的最短距离,现在我们对所有图中原本存在的边的边的边权进行修正,考虑边$(u,v)$,我们将其新的边权设置为$W(u,v)+D(u)-D(v)$,由最短路性质我们知道$D(u)+W(u,v)\geq D(v)$,因此我们可以得知所有边的新的边权一定非负。

现在考虑一条路径$v_1,v_2,\ldots, v_k$,它的修正后的距离为

而$D(v_1)$和$D(v_k)$是已知的常数,因此我们可以保证在边权修正之前和修正之后两点之间的最短路是同一条。因此现在的问题就变成了在一个所有边权非负的图上找最短路。

带修改的最短路问题

题目1:给定$n$个顶点$m$条带权边(权重非负)的无向连通图,以及一个指定的顶点作为起点。之后$q$个请求。第$i$个请求分两类,第一类查询从起点到某个顶点$x_i$的距离,第二类增大$c_i$条边的权重,增大的总和不超过$M=10^5$。其中$1\leq n,m\leq 10^5$,$1\leq q\leq 10^3$

很显然我们可以每次修改完成后都跑Dijkstra重新计算距离,这样时间复杂度为$O(q(n+m)\log_2n)$。有点大,但是可以用另外一个技巧将其中的$\log n$去掉。

具体的做法就是我们可以用类似Johnson算法的技术,先得出每个顶点到起点的最短路径,记第$i$个顶点的最短距离为$D_i$。之后我们修正每条边的权重为$w'(u,v)=D(u)+w(u,v)-D(v)$。由于最短路保证了$D(u)+w(u,v)\geq D(v)$,因此每条边修正后的权重还都是正数。类似于Jonnson算法,原图最短路也对应新图的最短路,因此我们可以通过在新图计算最短路就可以找到原图的最短路。

下面说这样做的好处是啥。在新图中,每个顶点到起点的最短路距离都是$0$。这是一个有用的性质,接下来考虑到所有边全权重增大的上限为$M$,因此我们可以保证新图修改过边权重后,所有顶点的最短距离均不会超过$M$。因此我们可以用Dijkstra一节中提到的优化技巧,不维护有限队列,转而维护$M$个普通队列,并按照编号从小到大进行处理,这样每次修改请求的时间复杂度就降低到了$O(M+n+m)$,而查询请求为$O(1)$。总的时间复杂度为$O(q(M+n+m))$。

一道题目

题目2:给定$n$个顶点$m$条无向带权边构成的连通图,指定起点和终点。之后$q$个请求,第$i$请求询问,假如加入一条新的权重为$w_i$的新边$(u_i,v_i)$,要求回答起点到终点的最短距离(注意每个请求不会对之后的请求产生影响)。其中$1\leq n,m,q\leq 10^6$

很显然最短距离不会增加,但是有可能减少,减少仅发生在新的最短路一定经过$(u_i,v_i)$的情况下。如果我们预先用Dijkstra算法求出每个顶点到起点和终点的最短距离,那么每个请求都可以$O(1)$回答了。

时间复杂度为$O((m+n)\log_2n+q)$。

题目3:给定$n$个顶点$m$条无向带权边构成的连通图,指定起点和终点。之后$q$个请求,第$i$请求询问,假如删除原本编号为$e_i$的边,要求回答起点到终点的最短距离或者报告不连通(注意每个请求不会对之后的请求产生影响)。其中$1\leq n,m,q\leq 10^6$,且每条边的权重为$1$到$10^9$之间

我们可以通过tarjan算法将强连通分量缩点,这样就可以很容易找出起点和终点之间的所有的桥了。只有删除的边是桥才可能会影响起点和终点的连通性。接下来讨论的就都是起点和终点依旧保持连通的情况。

用Dijkstra算法求出任意一条最短路,将最短路上的边打上标记,并进行连续编号。

容易发现,删除只可能会让最短路增大。如果被删除的边不在最短路上,那么最短路不变,否则需要额外的讨论。

记被删除的边为$e$。我们先证明一个点,就是新的最短路$P'$中至少有一条边$x$,满足这条最短路同时也是原图中包含$x$的最短路,同时原图中所有包含$x$的最短路都不会包含被删除的边。证明比较复杂,可以发现包含某条边的最短路径,其前缀和后缀部分是由打标记的边组成的,即与标记的最短路有公共前后缀。而考虑新的最短路$P'$取出前缀和后缀中被标记的边后,剩下的中间部分$L$都是没有打过标记的边。

对于某条边$y$,如果在原图中包含$y$的最短路中同时包含$e$,那么如果$y$出现在$e$之前,称为第一类边,否则$y$出现在$e$之后,称为第二类边。很显然一条边不能同时为第一类边和第二类边。

现在我们证明至少存在上面提到的一条边$x$。通过反证法,假设所有$L$中的边要么是第一类边,要么是第二类边。很显然$L$的第一条边一定是第一类边,$L$的最后一条边一定是第二类边。这就允许进行二分,直到找到$L$上两条连续的边$(a,b)$和$(b,c)$。其中$(a,b)$是第一类边,$(b,c)$是第二类边。这意味从着从$b$到起点和到终点的最短路都会经过$e$,即从起点到终点经过$b$的最短路会经过两次$e$,由于所有边权重为正数,因此这显然是不可能的,命题得到证明。

利用上面证明的命题,我们的算法就得出来了。我们可以暴力枚举所有边,统计其所在最短路不含哪些打标记的边(很显然这些边的编号是某个区间)。之后我们可以区间更新这些没出现的标记过的边,记其被删除后的最小值可能为某个数,由于是区间更新,所以可以用线段树加速。

最后总的时间复杂度为$O((n+m)\log_2n+q)$。

题目4:给定$n$个顶点$m$条无向带权边构成的连通图,指定起点和终点。之后$q$个请求,第$i$请求询问,假如修改编号为$e_i$的边的权重为$w_i$,要求回答起点到终点的最短距离(注意每个请求不会对之后的请求产生影响)。其中$1\leq n,m,q\leq 10^6$,且每条边的权重为$1$到$10^9$之间

设被修改的边为$e$,那么可以分两类情况讨论,新的最短路是否包含$e$。如果是,非常简单,枚举$e$的两个端点到起点和终点的距离即可。如果不是,那么我们删除$e$也无妨,这就变成题目3所讨论的内容。

总的时间复杂度为$O((n+m)\log_2n+q)$。

提供一道题目

题目5:给定一个$n\cdot m$的矩阵。初始的时候矩阵中每个单元包含一个数$1$,一个单元格与上下左右四个单元格相连(如果某个边界不存在单元格,则可以从这个边界离开矩阵)。要求回答$q$请求,请求分两类。

  1. 将某个单元格中的数从$1$改成$0$。
  2. 查询从某个单元格出发离开矩阵,希望经过的所有顶点上数值的总和最小,问最小的总和是多少。

这里$1\leq n,m\leq 500$,$q\leq 10^6$。

我们可以始终维护边界到某个顶点的最短路径的长度(我们将数值和看成长度)。初始时候的最短长度非常好算,因为只可能沿着四个方向走到底。

由于我们一直为每个单元格维护最新的最短路信息,因此请求2都是能$O(1)$回答的。

下面考虑请求1,将某个单元格中的数改成$0$。我们发现首先到这个单元格的最短路一定减少了$1$,并且边上的一些顶点的最短距离可能也发生了改变。这里我们可以用spfa的松弛技术,将这个单元加入到队列中。之后不断向四周进行松弛。

上面的操作看起来比较暴力,但是实际上非常快。由于每个顶点入队,最短距离一定会减少,而每个顶点的初始最短路径均不超过$O(\min(n, m))$,因此这个顶点入队的次数最多也只是如此。总的松弛的时间复杂度为$O(nm\min(n,m))$。

总的时间复杂度为$O(nm\min(n,m)+q)$。

这道题和题目$1$有些类似,都借助了最短路的一些特殊约束。

提供一道题目

题目6:给定一副包含$n$个顶点$m$条边的有向图,每条边都有边权。且从顶点$1$到其余顶点都至少存在一条路径。且保证初始时顶点$1$到每个顶点的最短距离不超过$1000$。接下来有$q$个请求,请求分为两类:

  1. 加入一条新的边$(u,v)$,权重为$w(u,v)$。
  2. 查询从顶点$1$到某个顶点$u$的最短距离。

其中$1\leq n,m\leq 10^5, 1\leq q\leq 10^5$。

这个问题和题目5实际上是一样的解法。我们维护最新的最短路信息。这样每当加入一条边的时候,边的两端最多只有一个顶点被松弛。而每个顶点被松弛时都会导致最短距离减少,因此每个顶点被松弛最多发生$1000$次,维护实时最短路信息的总的时间复杂度为$O(1000(n+m+q))$。由于我们维护了实时信息,因此请求2可以直接$O(1)$回答。总的时间复杂度为$O(1000(n+m+q))$。

最小环算法

Floyd求法

Floyd算法也可以用于解决最小环问题。所谓的最小环问题,是指在图中找到一个总边权最小的长度至少为3的简单环,时间复杂度为$O(V^3)$。

考虑最小环C,设C上编号最大的顶点为x,记x左右两边的顶点为u,v,C上边的总权重为c,那么必定有

我们可以在Floyd流程套入计算最小环的过程。

c = INF;
for(k = 1; k <= n; k++){
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            if(i != j && edges[j][k] && edges[k][i]){
            	c = min(c, D[i][j]+D[j][k]+D[k][i]);
            }
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            D[i][j] = min(D[i][j], D[i][k]] + D[k][j]);
        }
    }
}

有向图最小环

要求有向图的最小环,可以通过全源最短路径实现。以每个顶点作为源,找到回到自己的最短路,这样就构成了最小环。从这些最小环中取最小的,就是我们要求的结果。

用Dijkstra算法总的时间复杂度为$O(V(V+E)\log_2V)$,如果是单位权图,那么可以用BFS算法将时间复杂度优化到$O(V(V+E))$。

无向图最小环

如果图中有自环,那么我们就找到了最小环,长度为1。否则如果图中有重边,我们就找到了最小环,长度为2,接下來仅考虑无自环和重边的简单图,这时候环的长度至少为$3$。

由于最小环中必定含有一个顶点,因此对每个顶点枚举包含它的最小环,之后合并后就能得到整个图的最小环。那么下面我们要解决的问题是:给定某个顶点$r$,找到包含它的最小环。

我们可以算出以$r$为源的单源最短路径(如果有多条,我们任选一条),之后由于每个顶点(除了$r$)的最短路都有前驱顶点,我们将前驱顶点作为树父,这样就形成了一株以$r$为根的树。

这里我们将除了$r$外顶点进行标记,对于顶点$v$,如果到$v$的最短路为$r=x_1,x_2,\ldots, x_k=v$,那么$v$的标记为$x_2$,记作$tag(v)$。于是每个顶点都得到了一个标记(除了$r$)。现在考虑一条边$(u,v)$,其中$u$与$v$均不是$r$,且$tag(u)\neq tag(v)$,那么我们就找到了一个有效环$r..u,v..r$。

上面这个算法我没有严谨的证明。

时间复杂度和有向图是相同的,用Dijkstra算法总的时间复杂度为$O(V(V+E)\log_2V)$,如果是单位权图,那么可以用BFS算法将时间复杂度优化到$O(V(V+E))$。

提供一道题目

一类最小瓶颈路问题

问题1:有无向图,有n个顶点,m条边。你从顶点1出发,去往顶点n。每条边上有一个机关,第i条边会使你损失$c_i$点血量。一旦你血量为负数,那么就会回到起点。每当你抵达一个顶点时,你的血量会完全恢复。问至少需要多少血量,才能保证你能顺利抵达顶点n。

这个问题有比较简单的做法,二分血量,每次校验时,将所有伤害低于血量的边加入,之后判断顶点1和顶点n是否连通即可。时间复杂度为$O((n+m)\log_2m)$。

问题2:有无向图,有n个顶点,m条边。每条边上有一个机关,第i条边会使你损失$c_i$点血量。一旦你血量为负数,那么就会回到起点。每当你抵达一个顶点时,你的血量会完全恢复。现在有Q个询问,每个询问指定一个起点和终点,问分别至少需要多少血量才能顺利从起点出发抵达终点。

这个问题可以通过整体二分解决,总的时间复杂度为$O((m + q)\log_2n\log_2m)$。另外一种做法就是观察出对于起点是u,终点是v的时候,我们实际上要求的从$u$到$v$的最小瓶颈路,而已知最小生成树中每对顶点之间存在的唯一路径都是二者之间的最小瓶颈路,因此我们只需要找到最小生成树,之后用LCT维护整棵树,每个请求都可以以$O(log_2n)$的时间复杂度统计。

问题3:有无向图,有n个顶点,m条边。每条边上有一个机关,第i条边会使你损失$c_i$点血量。一旦你血量为负数,那么就会回到起点。顶点分成两类,第一类顶点具有恢复生命的能力,第二类顶点则没有。现在有Q个询问,每个询问指定一个起点和终点(起点和终点都是第一类顶点),问分别至少需要多少血量才能顺利从起点出发抵达终点。

首先为每个第二类顶点算出其距离最近的第一类顶点的最短距离(利用多源最短路算法)。之后记$d(u)$表示第二类顶点u到最近的第一类顶点的距离。之前我们判断一条边加不加入是靠边的伤害是否不高过血量,现在我们需要修改判断的标准,对于边$e_i=(a,b)$,当且仅当血量不低于$d(a)+d(b)+c_i$。之后问题转换为最小瓶颈路问题,用整体二分或者LCT都可以。

这边说明一下原因好了,假设血量上限为$x$。我们可以定义状态$(i,j)$表示位于顶点i上,并且有j滴血量。我们可以在图上进行搜索来判断是否可以从某个顶点移动到另外的顶点。如果i是第一类顶点,那么由于恢复的效果,因此$(i,x)$可以从$(i,j)$转移抵达,换言之,我们从$(i,j)$到$(i,x)$加上一条有向边。但是i是对于第二类顶点的情况,那么如果$j<d(i)$,那么很显然不能从$(i,j)$转移到血量更高的状态,这也意味着这些状态无法转移到任意顶点为终点的状态,我们可以直接无视这些状态。现在考虑$(i,j)$,其中$x-d(i)\geq j\geq d(i)$,那么我们可以先从这个顶点出发到达最近的第一类顶点之后再次回到当前顶点,从而血量提高到$x-d(i)$,因此我们从$(i,j)$向$(i,x-d(i))$连一条边。事实上,对于任意$(i,j)$,其中i是第二类点,$j>x-d(i)$,都是不可达的,因此我们也可以无视这些状态。

现在我们可以将上面提到的状态和转移进行压缩,我们可以认为顶点$i$对应的就是状态$(i,x-d(i))$(这是可达的并且可以通过后续转移抵达某个第一类顶点的最优状态)。现在我们考虑边$e_k=(a,b)$,我们是否可以从$(a,x-d(a))$转移到$(b,x-d(b))$呢,这要求我们经过边$e_k$从a到b后剩余的血量至少不少于$d(b)$,即$x-d(a)-c_k\geq d(b)\Rightarrow x\geq d(a)+d(b)+c_k$。这就是题解中公式的由来。

问题4:有一颗有$n$个顶点的树$T$,顶点分成两类,第一类具有恢复效果,第二类则没有。经过第$i$条边,会受到$c_i$点伤害($1\leq c_i\leq 5$。初始的时候或者抵达第一类顶点的时候血量会恢复到$k$(一旦血量为负则会直接失败)。现在给出$q$个请求,每个请求给定两个顶点$(u,v)$,要求回答是否有可能从$u$出发抵达$v$,不保证$u,v$是第一类点。

如果能保证每次起点和终点都是第一类顶点的话,这个问题实际上就成为了问题$3$的弱化版。但是这里不保证。

如果没有第一类顶点,那么我们每次只能选择最短路,这条路是树上的唯一路径。因此比较一下血量不小于路径长度即可。

首先我们将所有边切分成单位为0.5的边(比如边的伤害为2,我们就切成四条边,中间创建三个临时顶点)。这样一条边最多切成了$10$条边,而我们可以对应的将血量翻倍。现在问题就成了有一副图,经过每条边都会受到一点伤害,而你的血量是$2k$。

我们可以尝试建立这样一幅图$G$,如果两个第一类顶点的距离不超过$2k$,那么我们可以自由通行与这两个顶点之间,于是我们在$G$上将这两个顶点上建立一条边。对于图$G$,如果两个顶点连通,那我们对应的在树上就可以进行相互转移。由于图$G$只有连通性有用,因此我们可以直接通过维护一个并查集实现。可以证明任意一个$G$中连通块对应的都是一株原树的子树(连通块在$T$中依旧保持连通)。

下面我们考虑怎么求$G$,我们当然可以对每个顶点跑一次单源最短路,但是这样太慢了。我们可以对于每个第一类顶点$v$求出距离它小于等于$k$的顶点,并将它们并入到$v$所在的连通块中。这样任意两个距离不超过$2k$的顶点对,它们的连通块必定会有交集。当然这样求$G$还是太慢了,我们可以换一种做法。先以所有第一类顶点作为起点抛出多源最短路径。之后如果某个顶点$x$距离最近的第一类点$y$的距离小于$k$,那么它的邻近的顶点$z$自然是属于$y$所在的并查集的,事实上我们可以保证$x$与$y$属于相同的并查集,因此我们只需要将$x$与$z$合并即可。这样我们只需要$O(n+n\alpha(n))$的时间复杂度就可以算出$G$中的所有连通信息了。

现在考虑一个请求$u$到$v$。很显然对于一个请求,我们有两种选择,第一种就是不在任何第一类顶点上休息,第二种就是进行了至少进行了一次休息。第一种请求求一下树上路径长度即可,通过差分+求LCA就可以直接解决。下面考虑第二种情况。这时候我们发现$u$到$v$的路径上被切分成若干段,每一段都属于$G$上的不同连通块。第二种选择的策略实际是这样的,我们先移动到某个连通块的边缘顶点$x$,之后去往同一连通块中最近的第一类顶点恢复,之后转移到距离$v$最近的且与当前所在第一类顶点在属于相同连通块的某个顶点$y$,之后从所在处去往$v$。

但是这里我们抵达$x$后需要保留$k$点血量以保证能到达最近的第一类顶点,同理$y$由于与$v$不属于相同的连通块,因此$y$距离一定处于所在连通块的边缘,即此时剩余的血量正好为$k$。

换句话说,$u$到$x$的距离不能超过$k$,而$y$到$v$的距离也不能超过$k$。现在问题变成,如果两个人分别从$u$最多走$k$步,$v$最多走$k$步,问是否有可能两个人最终处于相同的连通块。

考虑到$G$上的连通块是对应$u$到$v$路径上连续的一段,而$u$到$v$的距离超过$2k$。于是乎显然我们应该向彼此尽量靠近,即分别向对方走$k$步,最后判断一下是否处于相同的连通块即可。

提供一道CF题目

Erdos-Gallai定理与Havel–Hakimi算法

给定一个包含$n$个顶点的无向简单图(无重边),以及每个顶点的度$d_1,d_2,\ldots,d_n$,问是否存在这样的图,如果存在就构造出来。

如何判断图是否存在.首先有解的前提是度数之和为偶数且所有度数非负。

Erdos-Gallai定理给出了一种$O(n)$时间复杂度的检查方法。其命题如下:

假设度数从大到小排序,$d_1\geq d_2\geq \ldots \geq d_n$,那么如果对于所有$1\leq k\leq n$,下面公式都成立,那么就有解,否则无解。

这个公式可以通过一些预先处理,在$O(n)$时间复杂度内计算完成。

那么现在知道有有没有解后,如何构造一组解呢。

很显然构造一组解的时间复杂度至少为$O(D)$,其中$D$是所有顶点的度数的和。我们可以用 Havel–Hakimi递归算法来实现。方法如下,我们将所有顶点按度数从大到小排序后,顶点$1$与$2,3,\ldots, d_1+1$建立一条边。之后我们递归解决剩下的包含$n-1$个顶点且度数分别为$d_2-1,d_3-1,\ldots, d_{d_1+1}-1, d_{d_1+2}, \ldots, d_n$的无向图构建问题。

Havel–Hakimi算法的总的时间复杂度为$O(n^2)$,排序可以选择将修改部分和未修改部分合并或基数排序。

支配树

详细的内容可以见CF博客

支配树可以解决这样一类问题:

给定一副有$n$个顶点$m$条边组成的有向图(允许有环),并选择一个顶点$r$作为根。对于可以被$r$访问到的每个顶点$v$,找到所有顶点$u$,满足删除$u$后,无法从$r$移动到$v$。这样的顶点对$u,v$,称作$u$支配$v$。

我们会发现支配关系满足传递性和反对称性。于是我们可以将支配关系建立成一个以$r$为根的树形图,一个顶点被其所有祖先顶点支配。

支配树可以以$O(n+m\log_2n)$时间复杂度内进入。

提供一道luogu模板题

那么建立了支配树后,如何判断某个顶点是否支配另外一个顶点呢,判断两者的LCA是否是前者即可。提供一道支配树+LCA的CF题目

二分图邻集问题

问题1:给定一个二分图,左边有$L$个顶点,右边有$R$个顶点,以及$m$条边。右边第$i$个顶点上都写了一个正整数$a_i$。对于$L$的任意子集$S$,记录$N(S)$表示$S$的邻集,而记$f(S)$表示$S$的邻集上的数字之和。现在问所有$2^L$个$L$的子集$S_1,\ldots,S_{2^L}$,要求计算$gcd(f(S_1),\ldots,f(S_{2^L}))$,其中$L,R,m\leq 10^6, a_i\leq 10^{12}$

首先如果有多个右边顶点,它们的邻集相同,那么就将它们合并成一个顶点(因为会被同时选择),而权重为这些顶点的权重之和。

假设结果为$g$,那么$g$一定是$\sum_{i=1}^Ra_i$的因子。我们可以一开始枚举$g=\sum_{i=1}^Ra_i$。之后如果所有右边顶点的权值都能整除$g$,那么显然不可能有更小的结果了,这时候就可以直接退出。

否则,我们找到权值不能整除$g$的右边顶点中,度数最小的那个顶点$v$,之后我们选中$L/N(v)$。对于度数能整除$g$的左边顶点,是否选中不会影响结果,而对于不能被$g$整除的其余顶点,我们会发现由于不同顶点的邻集不同,且$v$的邻集是其中最小的,因此该顶点的某个邻接顶点一定属于$L/N(v)$。

之后我们来计算$f(L/N(v))$在模$g$的时候的值,很显然值恰好为$\sum_{i=1}^Ra_i-a_v\mod g$。这个值不是0,即$f(L/N(v))$的总权不能整除$g$,这意味着我们可以得到更小的公约数。

由于$g$最多减少$\log_2 10^{18}$次,因此总的时间复杂度为$O(m+L+R\log_210^{18})$。

其实还可以简化一下,因为得到的结果一定是所有顶点权重的最大公约数的倍数,而上面的过程直到所有顶点权重能整除结果的时候才退出,因此可以得出结果一定是所有顶点(这里的顶点是合并后的顶点)权重的约数。由于最终问题变成了求一组数的最大公约数,而这个算法的时间复杂度为$O(m+L+R+\log_210^{18})$。

提供一道CF题目

竞赛图(Tournament)

竞赛图是指将一个完全图中的所有边转换成一条单向边得到的有向图。

命题1:如果竞赛图无环,那么竞赛图的拓扑序是唯一确定的

由于无环,因此可以进行拓扑排序。即存在唯一一个顶点(任意两个顶点之间有边,因此这里唯一)出度为0,对应的入度为$n-1$。我们删除这个顶点后,其余所有顶点的出度都对应减少1。而无环竞赛图的子图还是无环竞赛图。重复这个流程,直到所有顶点被删除。这样就得到了唯一确定的拓扑序。

命题2:竞赛图的强连通分量缩点后呈链状

由于竞赛图的连通分块两两有边,且无环。因此我们将连通分块缩点后,得到的是一个更小的无环竞赛图。根据命题1知道它的拓扑序是唯一确定的,因此呈现链状。

命题3:如果竞赛图是强连通的,则一定存在一条哈密顿回路

设$n$为竞赛图的顶点数目。

从竞赛图中任选一个顶点$r$,将竞赛图中有出边到$r$的顶点集合记作$X$,其余顶点记作$Y$。很显然两个集合都不空(否则不可能是强连通分量)。

现在考虑两种情况,如果删除顶点$r$后,剩下的竞赛图依旧强连通,那么我们可以通过归纳法,可以找到其余顶点组成的长度为$n-1$的哈密顿回路。由于是回路,因此存在两个回路中相邻的顶点$u,v$,其中$u\in X$且$v\in Y$。我们可以将$r$插入到回路的$u,v$之间。

否则竞赛图不强连通,此时竞赛图的强连通分量之间呈现链状,且存在链头的某个顶点$v$和链尾的某个顶点$u$,满足边$(r,v)$与$(u,r)$存在。我们可以通过构造法,生成一个长度为$n-1$,且从$v$开始到$u$结束的哈密顿路径,之后加入顶点$r$到路径尾部就得到了回路。

命题4:竞赛图存在一条哈密顿路径

如果竞赛图是强连通的,根据命题3,可以构造一条哈密顿回路。否则竞赛图非强连通,我们可以直接用归纳法处理。

命题5:大小为$n$的竞赛图如果强连通,则恰好有长度为$3,4,\ldots,n$的简单环。

由命题3知道强连通竞赛图一定有哈密顿回路,对应的就是一个简单环。其余环可以通过在哈密顿回路中的$X$集合顶点或$Y$集合顶点删除一些顶点得到。

兰道定理(Landau's Theorem):一个出度序列$a_1\leq a_2\leq \ldots \leq a_n$,可以构建一个竞赛图当且仅当满足:$\sum_{i=1}^ka_i\geq {k \choose 2}$且当$k=n$时等号成立

必要性不必多说,说一下充分性。

我们可以提前构建一个大小为$n$的无环竞赛图$B$,记$b_i$为第$i$个顶点的出度,且出度满足$b_i=i-1$。

之后我们来考虑如何构造一组解。

如果序列$a$与$b$不同,考虑找到最小的$i$,满足$a_i\neq b_i$。由于无环竞赛图的特殊性质有$\sum_{i=1}^kb_i={k \choose 2}\leq \sum_{i=1}^ka_i$,因此这里一定有$a_i>b_i$。对应的由于$a$序列和$b$序列拥有相同的总和,因此一定存在某个下标$j$,有$a_j<b_j$,且$i<j$。注意到$b_j>a_j\geq a_i>b_i$,因此$b_j\geq b_i+2$。这意味着至少存在某个顶点$t$,$b$到$t$为出边,且$t$到$b$为出边(即存在边$(j,t),(t,i)$)。我们反转这两条边的方向,这样$t$的度数不变,但是$j$的出度减少了$1$,而$i$的入度增加了$1$。且还能发现$b$序列的任意前缀和依旧小于$a$序列的前缀和。

因此不断这与操作,我们就能将构建一个度数指定的竞赛图了。

问题1:给定一个拥有$n$个顶点的竞赛图。告诉你这${n\choose 2}$条边的方向,要求找到其中一个顶点,这个顶点到其它所有顶点都存在一条路径。

当顶点数只有1的时候,很容易求解。现在假设顶点数为$n$,且我们找到了$1,2,\ldots,n-1$的导出子图的一个满足条件的顶点$v$。现在考虑顶点$n$和$v$,如果从$n$到$v$有一条边,那么$n$到其余顶点就都有路径了,同理如果$v$到$n$有一条边,$v$到其余顶点也都有路径了。

问题2:给定一个拥有$n$个顶点的竞赛图。每条无向边有可能有两种颜色,粉色或绿色。现在已知所有粉色的单向边的方向,但是所有绿色边都是未知的。现在要求使用最多$n$次请求,每次请求询问一条绿色边的方向。要求找到其中一个顶点,这个顶点到任意其它顶点,都存在一条仅使用一种颜色边的路径。

首先我们仅考虑粉色边的存在,用tarjan算法处理出强连通分量。

如果此时入边为0强连通分量数目为1,那么任取该强连通分量中的任意顶点作为根即可。否则我们取两个入度为0的不同强连通分量,并从每个强连通分量中各取一个绿边入度为0的顶点,这样一次查询至少一个顶点入度变成了1。如果一个强连通分量中所有顶点的绿边入度都变成了1,就删除这个强连通分量。重复这个操作,直到满足推出条件。

证明一下算法的正确性,首先找到的根由于绿边入度为0,其它顶点要么绿边入度为1,要么就能被根访问到。由于绿边不存在环,因此绿边入度为1的顶点都能被根访问到。

之后每次询问一个顶点入度从0变成1,因此最多发生$n-1$次查询。

一道CF原题

题目3:给定一个拥有$n$个顶点的竞赛图,要求找出图中所有不同的强连通导出子图(两个强连通导出子图不同当且仅当顶点集合不同),输出它们的顶点集合。$n\leq 23, m\leq n^2$

这道题需要用到竞赛图的特殊性质。竞赛图生成的强连通分量之间是链状关系。这意味着我们可以为竞赛图中的极大强连通分量排序,记第$i$个强连通分量为$S_i$,如果$i\leq j$,且$a\in S_i,b\in S_j$,那么从$a$到$b$一定存在一条路径。因此我们可以维护一个函数$scc$,其中$scc(x)$表示状态为$x$的导出子图(二进制表示)的编号最小的极大强连通分量中的顶点。之后我们考虑如何计算$scc(x)$,对于任意$x$中的顶点$u$,如果从$u$到$scc(x-u)$中的任意一个顶点有至少一条边,那么$u$一定属于编号最小的强连通分量,即$u\in scc(x)$,对所有$x$中顶点进行考虑即可求出$scc(x)$。

接下来我们来判断一个导出子图$x$是否是强连通的,它是强连通的当且仅当所有顶点位于编号最小的极大强连通分量中,即$scc(x)=x$。

总的时间复杂度为$O(n2^n)$。

推荐一道题目SRM783的RecursiveTournament。

强连通分量

一个有向图是强连通的,当且仅当图中任意两个顶点之间存在一条有向路径。

一个无向图是强连通的,当且仅当图中不存在割边。

一个强连通分量是极大的,当且仅当不存在任意一个它的超集也是强连通的。

我们可以用tarjan算法$O(V+E)$时间复杂度内求出一个有向图和无向图的所有极大强连通分块。

用强连通算法可以解决很多问题。

问题1:给定一个有$n$个顶点和$m$条边的有向图,之后给定$Q$个请求,每个请求指定$u,v$,要求判断是否存在一个包含$u$和$v$的环路。其中$n, m, Q\leq 10^6$

存在包含$u$与$v$的环路当且仅当二者处于同一强连通分量。用tarjan算法解决,时间复杂度为$O(n+m+Q)$。

子图状压问题

问题1:给定一个$n$个顶点的完全无向图,问有有多少不同的生成连通图,即存在多少边集的不同子集,仅考虑这些边,所有顶点连通。

要统计有多少连通图,我们只需要统计有多少不同的非连通图,之后用总子集数$2^{n\choose 2}$减去它即可得到结果。

对于任意一个非连通图,顶点$1$所在连通块大小一定小于$n$。而当顶点$1$所在连通图$S$确认时,对于两个端点都不在$S$中的边,其出现与不出现都可以,但是一个端点落在$S$中的边,一定不出现,而所有两个端点都落入$S$中的边,一定要保证$S$的连通性。

可以发现我们要想求一个大小为$n$的图的连通图数目,需要求大小为$n$的图的不连通图数目,而这可以分解为求一个大小小于$n$的图的连通图数目问题。因此我们这里有效缩小了问题的范围。记$f(n)$表示大小为$n$的完全图,连通图数目。可以得出递推公式:

我们可以直接暴力求解上面的公式,在认为高精度运算(结果范围不会太大)时间复杂度是常数的前提下,得到的时间复杂度为$O(n^2)$。

提供一道POJ题目

问题2:给定$n$个顶点$m$条边的无向图(可能有重边和自环),要求统计每个导出子图的边集大小,按排序从小到大输出。其中$n\leq 20,m\leq n^2$。

我们记$C(i,j)$表示顶点$i$和$j$之间存在的边数,这个很容易预处理出来。我们可以定义$f(S)$表示$V$的子集$S$对应的导出子图的边集大小。那么我们可以从$S$中取任意一个元素$v$,并记录$S'=S-v$。那么可以得出递推公式:

上面的算法的时间复杂度为$O(n2^n+m+n^2)$,空间复杂度为$O(2^n+n^2)$。

问题3:给定$n$个顶点$m$条边的无向图(可能有重边和自环),要求回答$q$个请求,每个请求选择两个不相交的$V$的子集$A$和$B$,要求计算有多少边一侧端点落在$A$,另外一侧端点落在$B$。其中$n\leq 20,m\leq n^2,q\leq 10^7$。

我们利用问题2的方式求解出每个导出子图的边集大小。之后记$g(A,B)$表示集合$A$与集合$B$之间的边的数目。记录$C=A\cup B$,可以发现$C$的导出子图中的边分成三类,两端都属于$A$,两端都属于$B$,一端属于$A$一端属于$B$,因此可以推出递推公式:

时间复杂度为$O(q+n2^n+m+n^2)$,空间复杂度为$O(2^n+n^2)$。

问题4:给定$n$个顶点,$m$条边的无向图,计算有多少边的子集,能使得图连通。其中$n\leq 15, m\leq 200$。

这道题和问题1类似。要计算多少连通图,我们只需要统计有多少不同的非连通图,而要统计有多少非连通图,我们可以通过统计包含$1$的连通图的数目再乘上某个因子。但是这里不保证是完全图,但是做法还是类似的。

用状态压缩技术,我们可以定义$h(S)$表示$V$的子集$S$的导出子图中连通图的数目。现在我们可以得出递推公式,记$E(S)$表示集合$S$的导出子图的边集。可以推出递推公式:

通过预处理,这个方法的时间复杂度是$O(n2^n+3^n)$。

问题5:给定$n$个顶点,$m$条边的无向图,要求对于所有$n-1\leq k\leq m$,计算有多少大小为$k$的边集的子集,能使得$n$个顶点连通(这个结果记作$f(k)$)。其中$n\leq 15, m\leq 200$。

Topcoder 761 SpanningSubgraphs

目前不会。。Petr在他的博客给了做法,有兴趣的人可以参考。

现在会了。首先我们可以考虑这样一个函数$h(p)$,表示每条边都有$p$的独立概率被删除,问最后图保持连通的概率。

很显然$h(p)$是Reliability polynomial,其是Tutte多项式的变种,且是一个阶数不超过$m$的多项式。

要得到$h(p)$,我们可以通过插值法。对于给定的$p_0$,我们可以用问题1的相同方法$O(3^n)$求解出$h(p_0)$,同理,我们只需要计算出$m+1$个输入输出对,就可以得到$h(p)$,时间复杂度为$O(m3^n)$。

同时我们可以发现$h(p)=\sum_{i=0}^mf(i)p^{m-i}(1-p)^i$。我们可以从$h(p)$的系数中提取出$f(i)$。

总的时间复杂度为$O(m3^n+m^3)$。

Tutte多项式

无向图$G=(V,E)$的Tutte多项式的定义为:

其中$c(A)$表示仅保留$A$中的边,图中的连通块数目,对于$c(E)$同理。

可以看出$T_G(x,y)$的$x$项的最高指标为$|V|$,而$y$项最高指标为$|E|$。

Reliability polynomial

给定无向图$G=(V,E)$,每条边都有$p$的概率被删除,不同边的删除是独立的。问最后图保持连通的概率$R_G(p)$。

可以发现$R_G(p)$是$p$的$|E|$阶多项式。

图上亦或问题

考虑这样一个题目:给定一个序列$a_1,\ldots,a_n$,每个元素初始的时候都是$0$。之后由$m$次操作,第$i$次操作给定两个数$x_i$和$y_i$,你必须$a_{x_i}$或$a_{y_i}$中的一个亦或上1。且要求$m$次操作后$\sum_{i=1}^na_i$最小。

对于每个序列中的元素,建立一个顶点,对于第$i$个请求,我们可以在$x_i$和$y_i$之间建立一条无向边。对于不同的连通块,我们可以独立处理。现在仅认为只有一个连通块。

我们可以重新解释问题,我们希望为每条无向边与其一个端点匹配,称与某个顶点匹配的边数为这个顶点的匹配度,我们希望让拥有奇数匹配度的顶点尽可能少。同时我们发现,对于一条简单路径,我们如果取反上面的所有边(即让边与另外一个顶点匹配),我们会发现仅路径的起点和终点的匹配度的奇偶性会发生改变。因此我们可以生成任意一个生成树,并任选一个顶点为根。将每个奇度数的顶点到根的路径全部翻转,这样我们发现除了根外,其余顶点的匹配数都是偶数。根的匹配度决定与连通块中边数的奇偶性,如果边数为奇数,那么根的匹配度也是奇数,这是无法避免的(不可能所有顶点的匹配度都是偶数)。

上面的过程,可以$O(n+m)$完成。

上面这个题目还有一个经典的变形:给定一副简单无向图(无重边和自环),我们希望重复尽可能多次下述操作:选择一个三个顶点$x,y,z$,其中边$(x,y)$和$(y,z)$存在,删除这两条边。问我们可以最多执行该操作多少次,并输出一个最长的操作序列

这个问题和之前提到的问题是一样的。为啥。我们可以重新解释该操作,选择某个顶点$y$,删除与其相邻的两条边,问最多删除次数。这等价于将每条边与某个端点匹配,如果一条边和某个端点匹配,称与某个顶点匹配的边数为这个顶点的匹配度,记$deg(i)$为顶点$i$的匹配度。那么我们希望最大化的是$\sum_{i=1}^n\lfloor \frac{deg(i)}{2}\rfloor=\frac{m-\sum_{i=1}^n(deg(i)\mod 2)}{2}$。这等价于最小化拥有奇数匹配度的顶点。剩下的就和之前提到的问题是一样的了。提供一道题目

唯一路径问题

一条简单路径是指一个无重复的顶点序列,其中对于任意相邻的有序顶点对$u,v$,都存在$(u,v)$这条边。

一个顶点如果到其余顶点都有一条唯一路径,则称这个顶点为候选根。

如果是无向图,那么有候选根存在,则意味着图连通,且无环,这意味这是一颗树,此时所有顶点都是候选根。

如果是有向图,问题就变复杂了很多。假设$r$是其中一个候选根,那么以$r$为根的DFS树必然同时满足下面两个条件:

  • DFS树一定包含了所有顶点。
  • 对于所有的非树边,一定从后代指向祖先。

上面就提供了我们一个$O(V+E)$的算法来判断一个顶点是否是候选根。

下面我们考虑$r$是候选根的情况下,希望找到所有的候选根。我们当然可以用naive的$O(V(V+E))$算法,但是这太慢了,我们实际上可以加速到$O(V+E)$。具体原理是,考虑任意一个顶点$u$,$u$到其子树中的所有顶点都有唯一路径,因此我们需要保证$u$到其所有祖先顶点都有唯一路径。由于$u$可以到其某个祖先顶点,因此在$u$的子树中一定存在一个顶点$v$,以及$u$的某个祖先$a$,$(u,a)$是图中的一条边。如果存在两个这样的顶点,那么路径就无法保证唯一,因此这样的顶点应该恰好只有一个。现在我们从$u$到所有$a$的子树中的顶点都有唯一路径,可以发现如果$u$是候选根当且仅当$a$是候选根。因为$a$要到任意祖先顶点,都不会经过$u$和$u$子树中的顶点。

上面的过程,我们可以通过树上DP在$O(V+E)$求解。

提供一些题目:

一类图上标号问题

问题1:给定$n$个顶点$m$条无向边组成的连通图,要求给每个顶点赋予一个值,记第$i$个顶点的值为$x_i$。要求赋予的值满足$|x_i-x_j|\leq 1$当且仅当边$(i,j)$存在。判断是否有解,如果有解,就输出任意一组解。

CF的题目

感觉事实上是挺难想到的,我想到将这些顶点按照值进行分组,那么这些组之间应该构成一个有序的列表,同一个组内的顶点组成一个团,任意两个相邻的组之间的顶点的并集也是一个团。然后就没有然后了。

首先我们可以证明如果两个顶点$u,v$的邻接表不同(这里认为一个顶点与自己也是邻接的),那么这一定有$x_u\neq x_v$。否则则必定存在一个顶点$w$,$w\in adj(u)\land w\notin adj(v)$,通过交换$u,v$可以很容易得到这个性质的成立。如果$x_u=x_v$,那么$|x_w-x_v|=|x_w-x_u|\leq 1$,但是这是错误的,因为边$(w,v)$不存在。

同时可以证明在有解的前提下,如果我们把邻接表相同的顶点赋予相同的值,那么依旧是有解的。考虑两个邻接表相同的顶点$u,v$,则边$(u,v)$一定是存在的,因此$|x_u-x_v|\leq 1$。不妨让$x_v=x_u+1$,那么可以发现对于任意与$u,v$相邻的顶点$w$,一定有$x_w\in {x_u,x_u+1}$。可以发现我们在最终结果中将$x_v$从$x_u+1$修改成$x_u$不会影响结果的成立。

因此算法就是我们先合并所有邻接表相同的顶点。之后我们认为图上的每个顶点的邻接表都不同,且每个顶点需要赋予一个与其余顶点均不同的值。

如果一个顶点度数大于$2$,那么其至少有三个邻接的顶点,可以发现我们是无法正确赋值的。

接下来可以发现图中每个顶点的度数都不超过$2$,且图是连通的。那么只有两种情况,顶点构成了一条链表,或者构成了一个环。构成环的情况下,由于所有顶点的邻接表不同,因此环的长度至少为$4$,而在大于$4$的情况下,是无解的。而是链表的情况,我们可以很简单的赋值。

总的时间复杂度为$O(m+n)$,如果我们利用哈希表。

支配集

对于$V$的子集$S$,若对于任意一个顶点$v\in V-S$,其邻集$N(v)$中一定至少有一个$S$中的顶点。那么称$S$是支配集。所有支配集中最小的称为最小支配集。

对于图中的某个大小为$k$的连通块,其中$k>1$,其最小支配集的大小上界为$\lfloor \frac{k}{2}\rfloor$。因为我们可以搞出一个生成树,之后将偶数深度的顶点和奇数深度的顶点分成两个集合$A$和$B$,可以发现二者都是这个连通块的支配集,且$|A|+|B|=k$。

题目1:给定$n$个城市,可以在一些城市中安装雷达,雷达的作用范围是半径为$r$的圆,此时城市可以视作一个点。现在知道每个城市的坐标,问至少要安装多少个雷达,可以将每个城市覆盖在雷达范围内(雷达信号边缘也算是覆盖到)。其中$1\leq n\leq 30$

如果两个城市的距离小于等于$r$,我们在他们之间建立一条边。这时候可以发现我们实际上要选的是一个最小支配集。可以用暴力的做法$2^n$,但是加一些优化。

参考资料