集训队作业bia解题报告bytelandian information agency

1、Bytelandian Information Agency解题报告浙江 唐文斌BIA解题报告浙江 唐文斌问题描述BIA机构内部使用一个包含N台计算机的网络。每台计算机被标号为1.N，并且1号机是服务器。计算机被一些单向传输线连接着，每条数据线连接两台计算机。服务器可以向任何一台计算机直接或者间接的发送数据包。当BIA得到新的信息，数据被放在服务器上，然后通过网络分发到各台计算机。BIA的首脑在考虑如果一台计算机停止工作（例如被黑客攻击）将会发生什么，有可能一些计算机将因此得不到服务器上的数据。我们称这种计算机是critical的。如下图，有两台critical计算机1、2。1是服务器，而所有

2、1到3的数据都必须经过2。输入N , M （N为点数，M为边数） N5000 , N-1M200000接下来M行每行两个数表示每条连接线的出发计算机和接收计算机的编号。输出第一行有一个整数K表示critical计算机的数目第二行包含K个整数描述了所有critical计算机的编号。Sample Input4 51 21 42 33 44 2Sample Output21 2算法分析看到数据规模，我们一般不会打算枚举某一点，尝试删掉它，然后DFS检查是否存在某些点将不可达。因为这样做实在太慢了。可以发现，该问题图论中的一个经典问题非常的相似无向图求割点：给定一个连通的无向图，找出所有的割点。割点是

3、删除之后让图变得不连通的点。唯一的不同就是无向图变成了有向图。回忆求无向图割点的算法：对原图进行一次DFS，得到一棵DFS树T（原图连通，所以不是森林）。考虑树根Root，如果a和b都是Rootd的儿子，说明a无法通过非Root的点到达b，所以Root是割点当且仅当它有不止一个儿子。考虑非根节点u，再考虑u的某个儿子v。如果v以及v的子孙都不存在指向u的祖先的后向边，那么删除顶点u之后v以及v的子孙与i的祖先将不连通。所以u是割点当且仅当存在某个儿子v以及v的子孙都不存在指向u的祖先的后向边。计算Lowu表示u以及u的子孙相连的辈分最高的祖先的访问时间。当LowvEnteru 时（Enteru

4、表示DFS访问到的时间，v是u的儿子),v或者v的子孙存在通向u祖先的后向边。如果LowvEnteru，则不存在后向边，那么u也就是割点了。（这里所说的是非Root，Root要根据儿子数目来判断）。所以只需要DFS一次计算出所有的Enteru和Lowu,就可以找出所有的割点。我们不禁会想，这个算法对于有向图是否仍然适用呢？我们很容易就找到了反例：DFS树枝为红色边所示，我们发现，这里出现了一条横叉边。由于无向图的DFS过程中是不可能出现横叉边，而有向图则可能。所以我们不能直接套用上述算法，而需要对其进行修改。类似的，设Lowu通过非相关边 定义u的相关边，指一个DFS树中点u到Root路上的所

5、有边（直系边）可以到达u的最高祖先的DFS访问时间。一开始设所有Lowu = Enteru（自己可以到达自己）。 定义u的相关边，指一个DFS树中点u到Root路上的所有边（直系边）前向边(u-v)这是最简单的情况，只需要更新Lowv = Min(Lowu , Lowv)2） 后向边(u-v)这也是比较简单的情况，更新Lowv = Min(Lowx) （x是v的直系子孙且是u的直系祖先，包括u和v）。3） 横叉边(u-v)设Aces = LCA(u , v) LCA(u , v)指u,v的最低公共祖先,Least Common Ancestor ，可以发现，可以通过非相关边到达Aces到u路径

6、中的某个点的祖先也可以通过与v不相关的 LCA(u , v)指u,v的最低公共祖先,Least Common AncestorLowv = Min(Lowv , Min(Lowx) （x是Aces的直系子孙且是u的直系祖先，包括u和Aces)。根据DFS的性质，横叉边必然是从树的右边往左边连。所以我们处理的时候用逆DFS顺序。处理到点v的时候，检查每一条连向v的边，如果不是树枝边，则根据上面的讨论更新Lowv。下面简单讨论一下算法的实现。该算法中，需要动态的查询两个点的最小公共祖先，而且需要求u到u的k祖先 定义u的k祖先为u在DFS树中上方第k个点。u的1祖先即Fatheru , 2祖先为

7、FatherFatheru。类似定义的最小Low值。对于动态查询LCA，我们可以通过一次DFS得到一个欧拉序列，转换成RMQ（Range Minimum Query）问题，用Sparse table法在O(nlgn)的预处理后，得到询问复杂度为O(1)的方法。 定义u的k祖先为u在DFS树中上方第k个点。u的1祖先即Fatheru , 2祖先为 FatherFatheru。类似定义设STit 为 序列Ai . i + 2t 1中的最小值，那么STit = Ai (t = 0) = Min(STit -1 , STi + 2tt 1) (t 0)那么对于查询u到u的k祖先这段路仅中的最小Low值

8、，也可以使用类似的方法，用FWit表示i到i的t祖先路径中的最小Low值。方程同上。因为Low值是动态计算的，但是我们去查询某一段的时候，这段中的Low值必然已经得到。所以可以用记忆化的DP方法得到所要的答案。对于每次查询u到u的k祖先这段路仅中的最小Low值，我们要将这段路分解为若干个2的整幂长度的路径。所以这里需要O(lgn)的时间。计算ST和FW都是O(nlogn)的，由于每条横叉边都要O(lgn)的时间，时间复杂度为 O(M0lgn)(M0表示横叉边的条数)。所以总的时间复杂度约为O(mlgn)。上述算法已经可以较快的通过所有数据，但是没有看到问题的一个很有趣的现象。观察每次对横叉边的操作，我们每次求一个LCA，然后求边的起始点u到公共祖先Aces路上的最小Low值。请注意，我们是按照逆DFS序处理每一个点的。这代表什么呢？可以发现这样一个有趣的事实：每次求的LCA，与之前所求得的，要么拓扑无关，要么在拓扑序在其之前。于是，我们便想到了一个耳熟能详的名词路径压缩！由于上述的事实，如果我们把已经求过的路径压缩成一个点，用最小的Low值作为这个点的Low值并不影响算法。所以，我们每次找一条从u到Aces的路的时候，顺便把这段路压缩成一个点。用并查