ioi2016集训队第一次作业题解

CBAL题目大给定一个N个点（从1到N标号）M条边的有向图。请你统计无序对(XY(XY1X的路径，和一条从点1到点Y的路径，且两条路径除了点1以外没有公共点。1≤n≤0≤m≤数据集1（30分）数据3（50分）算法分基本概要解决这个问题，先要了解几对于一个有向图，如果从给定的起点到某个节点X的所有路径都经过节点X的必经点中离起点最远（X最近）X的最近必经点（immediatedominator），记idom[X]=Y。最近必经点是唯一的。将除起点外所有节点与最近必经点连接构成一棵树，称为支配树（DominatorTree。相乘并累加即是满足条件的无序对个数。因此本题的重点在于如何快速求出给定有向图的支配树。DAGG上的节点有严格的拓扑序，即只能从一个拓扑序靠前的点到达一个拓扑序靠后的点。在这种情况下，某个节点的最近必经点一定是拓扑序更小的点，我们可以按照拓扑序增量构造支配树。1～X1的节点组成的支配树，现在要加入节XX的节点，这些节点的最近公共祖先（LCA）就是节点X的最近必经点，据此将节点X加入支配树中。LCAO((NMlogN)30NMDFS，如果能到达某个节点，则被删除的点不是这个节点的必经点。忽略所有不可达点，时间复杂度O(NM)，能得到20分。结合DAG上的算法可以得到50分。快速算对于NM比较大的图，可以使用Lengauer-Tarjan算法计算Lengauer-Tarjan算法分为以下三个DFSDFS对于一个节点Y，存在祖先X能通过一系列节点pi（可以为0个）到达节点Y，且∀i,dfi>dfn[Y]，称节点X是节点Y的半必经点（semidominator），记semi[YX半必经点可以通过半必经点定理计算。半必经点定理描述对于一个节点Y，考虑所有能直接到达它的节点，设其中一个为dfn[Xdfn[Y]，此XZ，满dfn[Z>dfn[Y时，semi[Z]为可能的半必经点以上所有可能的节点中，DFS时间戳（dfn）最小的节点为Y的半必经半必经点不一定是必经点，需要通过必经点定理修正。必经点定理描Xsemi[X的路径上的其它节点，记其中半必经点时间戳最小的节点为Z；semi[Z]=semi[X]idom[X]=semi[Z̸=semi[X]idom[Xidom[Z]实注意到，在计算半必经点的过程中如果某个节点的前驱结点的时间戳比它大，需要这个前驱结点的所有时间戳比当前考虑节点大的祖先。计算最近必经点的过程中也要考虑它和半必经点之间的路径上的所有节点。可以按照时间戳逆序计算每个节点的半必经点，此时所有时间戳更小的节点仍未计算，在考察时间戳大的祖先时可以直接它在已计算节点森林中的所有祖先。已计算节点森林可以用并查集来实现。在计算最近必经点时，在某个节点刚被加入已计算节点森林时立即计算以它为半必经点的所有节点的最近必经点。O((NMlogN)1O(NM)，能得到本题所有算法相关Lengauer-Tarjan算法正确性的严谨证明，可见于“AFastForFindingDominatorsina1本题中并查集具有祖先关系，不能按秩合并。根据“Worst-CaseysisofSetUnionAlgo