ACM培训——图论(一)ppt课件.ppt

《ACM培训——图论(一)ppt课件.ppt》由会员分享，可在线阅读，更多相关《ACM培训——图论(一)ppt课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论（一）图论（一）四川大学ACM/ICPC集训队李冠一2013.7 百度百科：图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。个人理解：图论是ACM/ICPC中经常出现的一类题目。多见于中档题，当然也有神题神模型。图论相对好入门，图的BFS/DFS遍历几乎一个没有算法基础的人也可以掌握。但是，当研究深入之后，实际上图论包含着许多艰深而复杂的理论。当然，对于大多数普通的ACMer来说，我们首先要做的就是熟悉基本算法、掌握常见模型、提高建模思维

2、。一、图的一、图的BFS遍历遍历算法步骤：1、用dis数组表示各点距离起点S的距离。disi=-1表示i点还未被访问。用mapij表示i点和j点之间是否有边。2、将diss初始化为0，将其它点的dis初始化为-1。将S点入队3、while（队列非空）从队首出队一个元素u 对于所有跟u有边相连的点v:if(disv=-1)disv=disu+1;v入队 每个节点只会入队一次，也只会出队一次。每个节点只会入队一次，也只会出队一次。每个节点只会入队一次，也只会出队一次。每个节点只会入队一次，也只会出队一次。时间复杂度时间复杂度时间复杂度时间复杂度O(V+E)O(V+E)。基本性质：基本性质：基本性质

3、：基本性质：如果遍历的是如果遍历的是如果遍历的是如果遍历的是0-10-1边权图呢？边权图呢？边权图呢？边权图呢？队列中的节点距起点的最短距离单队列中的节点距起点的最短距离单队列中的节点距起点的最短距离单队列中的节点距起点的最短距离单调递增。调递增。调递增。调递增。且队首与队尾的最短距离差值不超且队首与队尾的最短距离差值不超且队首与队尾的最短距离差值不超且队首与队尾的最短距离差值不超过过过过1 1如果遍历的是如果遍历的是如果遍历的是如果遍历的是1-1-2 2边权图呢？边权图呢？边权图呢？边权图呢？1-2边权图的BFS：把每条长度为2的边中间加一个点，拆成两条边例题例题例题例题 1.11.1HDO

4、J 1180:诡异的楼梯诡异的楼梯 题意：在一个地图上，有一些位置是空地，有些位置有障碍。还有一些位置有梯子，不过梯子的方向有的是横向，有的是竖向，且方向每分钟变化一次。求从起点到终点的最短时间。解法：每次最多有五种状态可以选择：上、下、左、右、停留原地等待。设计状态时除了要保存距离以外，还要保存当前的时间是奇数还是偶数 这样才能在BFS时进行状态的转移二、图的二、图的DFS遍历遍历算法步骤（以算法步骤（以0-10-1边权图为例）：边权图为例）：1 1、从某个节点开始，每次任选一、从某个节点开始，每次任选一个与它相邻的未访问节点访问下个与它相邻的未访问节点访问下去去2 2、直到当前节点的所有相

5、邻节点、直到当前节点的所有相邻节点都已经被访问过。都已经被访问过。3 3、回溯到第一个未被访问过的节、回溯到第一个未被访问过的节点点三、拓扑排序三、拓扑排序概念引入：一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。算法步骤算法步骤1.从有向图中选取一个没有前驱的顶点，并输出；2.从有向图中删去此顶点以及所有以它为尾的边；3.重复上述两步，直至图空。*如果图不空，但找不到无前驱的顶点，说明图中

6、有环。拓扑序列：v6,v1,v4,v3,v2,v5注意：拓扑序列可能不唯一注意：拓扑序列可能不唯一拓扑排序的应用拓扑排序的应用判断一个有向图中是否有环。无环的图所有点都能进行拓扑排序。求DAG图最长路类似于课程安排问题的题目最小生成树 定义bchifaedg48812414791067211生成树：对于一个无向图，生成树是它的一个无回路的联通子图最小生成树：各边权值和最小的生成树有向图的最小有向生成树？有向图的最小有向生成树？最小树形图最小树形图最小生成树prim 算法 (复杂度O(n2)kruskal算法 (复杂度O(m*lg(m)Prim算法贪心准则加入后仍形成树，且耗费最小始终保持树的结

7、构Kruskal算法是森林算法过程从单一顶点的树T开始不断加入耗费最小的边(u,v)，使T(u,v)仍为树 u、v中有一个已经在T中，另一个不在T中Prim 算法过程bchifaedg488414791067211aidcbhgfe12Krustal算法 kruskal 算法思想：贪心选取最短的边算法思想：贪心选取最短的边来组成一棵最小的生成树。来组成一棵最小的生成树。具体做法：先将所有的边做排序，然后具体做法：先将所有的边做排序，然后利用利用并查集作判断来优先选择较小的边，作判断来优先选择较小的边，直到建成一棵生成树。直到建成一棵生成树。intkruskal()intans=0;sort(e

8、dge.begin(),edge.end();for(inti=0;iedge.begin();i+)if(reunion(edge.u,edge.v)ans+=edge.w;returnans;代码如下：代码如下：代码如下：代码如下：intfindp(intx)returnpx=-1?x:px=findp(px);boolreunion(intx,inty)intpx=findp(x);intpy=findp(y);if(px=py)returnfalse;ppx=py;returntrue;Prim 和 Kruskal的区别Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边：

9、对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kruskal,其选取的边(u,v)任意，只要这个边的加入不能使被覆盖的顶点构成回路。生成树计数生成树计数对于有n个点的图，构造一个矩阵，使得：若i=j，aij=dexi。（dexi为节点i的度数）。否则，若点i和点j间有边相连，aij=-1。若无边相连，aij=0。然后求这个矩阵的行列式，得到的即是这个图的生成树个数。有带权图G,对于图中每条边ei,都有benifiti(收入)和costi(花费),我们要求的是一棵生成树T,它使得(benifiti)/(costi),iT最大(或最小).解法：二分 or 迭代

10、根的度数不超过K的最小生成树。解法：迭代最优比率生成树解法：0-1分数规划设xi等于1或0,表示边ei是否属于生成树.则比率r=(benifiti*xi)/(costi*xi),0im.令：z=(benifiti*xi)-l*(costi*xi)两个性质:1.z单调递减证明:因为cost为正数,所以z随l的减小而增大.2.z(max(r)=0证明:若z(max(r)0,(benifiti*xi)-max(r)*(costi*xi)0,可化为 max(r)=0,根据性质1,当z=0 时r最大.单源最短路径问题单源最短路径问题单源最短路径=Single Source Shortest Path，即

11、在有向图（或无向图）中求解给定点到其他点之间的最短距离算法：算法：算法：算法：DFSDFS算法算法算法算法 DijkstraDijkstra算法算法算法算法Bellman-Ford算法算法SPFA算法算法用优先队列（二叉堆）优化用优先队列（二叉堆）优化用优先队列（二叉堆）优化用优先队列（二叉堆）优化dijkstra算法5、重复4、5直至所有的点都进入S1、集合S，表示已经找到最短路径的点。dis表示各点当前据源点的最短距离2、初始时，集合中只有源点。3、每个点u进入集合S时，用disu+mapuv更新所 有与它相连的节点v的disv。4、选取S外的点中dis最小的一个点进入S237184566

12、134105275934682演示：演示：求从求从1到到8的最短路径的最短路径237184566134105275934682X=1min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=0237184566134105275934682X=1,4min d12,d16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2p1=0p4=1p2=2237184566134105275934682X=1,2,4min d16,d23,d25,d47=min 0+3,2+6,2+

13、5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3p2=2p4=1p1=0p6=3237184566134105275934682X=1,2,4,6min d23,d25,c47,d67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X=1,2,4,6,7min d23,d25,d75,d78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,p5=6p2=2p4=1p1=0p6=3p7=3p5

14、=6237184566134105275934682X=1,2,4,6,7min d23,d53,d58,d78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X=1,2,3,4,6,7min d38,d58,d78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=102371845661341052759

15、34682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10void dijkstra(int s,int t)void dijkstra(int s,int t)ds=0;ds=0;q.push(make_pair(s,0);q.push(make_pair(s,0);while(!q.empty()while(!q.empty()int u=q.top().first;int u=q.top().first;int temp=q.top().second;int temp=q.top().sec

16、ond;q.pop();q.pop();if(temp!=du)if(temp!=du)continue;continue;for(int i=headu;i!=-1;i=nxti)for(int i=headu;i!=-1;i=nxti)int v=toi;int v=toi;if(dv=-1|dvdu+wi)if(dv=-1|dvdu+wi)dv=du+wi;dv=du+wi;q.push(make_pair(v,dv);q.push(make_pair(v,dv);例题例题 2.12.1POJPOJ34633463:Sightseeing:Sightseeing 题意：求最短路的种数，及

17、比最短路长题意：求最短路的种数，及比最短路长度长度长1的路的总数的路的总数解法一：解法一：解法一：解法一：dijkstradijkstra时不止要记录最短路长度，还要记录时不止要记录最短路长度，还要记录时不止要记录最短路长度，还要记录时不止要记录最短路长度，还要记录最短路最短路的种数，及比最短路长度少的种数，及比最短路长度少1的路的总数。每把一个的路的总数。每把一个点加入集合，更新点加入集合，更新disv的时候就要进行转移。当然，的时候就要进行转移。当然，如果如果disv发生了变化。那么之前的计数要清零。发生了变化。那么之前的计数要清零。解法二：解法二：解法二：解法二：预处理起点和终点到每个点

18、的最短距离预处理起点和终点到每个点的最短距离预处理起点和终点到每个点的最短距离预处理起点和终点到每个点的最短距离。比最短路。比最短路长长1的点，必定有且只有一条边不在最短路上。枚举。的点，必定有且只有一条边不在最短路上。枚举。那么，第那么，第K短路如何求呢？短路如何求呢？先预处理出终点到每个点的距离，作为启发函数。A*搜索时第k个被搜索到的节点的距离值即是第K短路的值Dijkstra算法的局限性如果边权为负值，Dijkstra算法还正确吗？求解右图A 至其他点的最短距离算法步骤：1）标记点A2）DistC=2最小，标记点C3）DistB=3最小，标记点B结束但是ShortestDistC=1A

19、BC23-2Dijkstra算法的局限性下图中，A至F的最短路径长度是多少？ABCDEF11-1-1-1-1-产生错误结果的原因产生错误结果的原因Dijkstra的缺陷就在于它不能处理负权回路：Dijkstra对于标记过的点就不再进行更新了，所以即使有负权导致最短距离的改变也不会重新计算已经计算过的结果我们需要新的算法Bellman-FordBellman-Ford算法思想Bellman-Ford算法基于动态规划，反复用已有的边来更新最短距离Bellman-Ford算法的核心思想松弛Distu和Distv应当满足一个关系，即Distvdu+wu,v则dv=du+wu,vfor 每条边(u,v)

20、如果du!=+且dvdu+wu,v则存在负权回路如果没有负权回路，那么任意两点间的最短路径至多经过n-2个点，因此经过n-1次松弛操作后应当可以得到最短路径如果有负权回路，那么第n次松弛操作仍然会成功，这时，最短路径为-应用：判断是否含有负环应用：判断是否含有负环应用：判断是否含有负环应用：判断是否含有负环时间复杂度算法复杂度为O(VE)其中V=顶点数，E=边数我们知道Dijkstra的算法复杂度是O(V2)，经过优化的Dijkstra算法可以达到O(V+E)logE)所以Bellman-Ford算法并不比它快，但实际上Bellman-Ford算法也是可以优化的Bellman-Ford算法的优

21、化在没有负权回路的时候，至多进行n-1次松弛操作会得到解，但实际上可能不到n-1次松弛操作就得到最优解了可以在每一轮松弛的时候判断是否松弛成功，如果所有的边都没有松弛的话，说明Bellman-Ford算法已经可以结束了进一步的优化SPFA算法SPFA=Shortest Path Faster Algorithm也即Bellman-Ford算法的队列优化。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛若某个相邻的点松弛成功松弛成功，则将其入队入队。直到队列为空时算法结束。void spfa(int s)memset(d,-1,sizeof(d);int front=0

22、,rear=0;Qrear+=s;ds=0;while(front!=rear)int u=Qfront+;inqu=false;for(int i=headu;i!=-1;i=nxti)int v=toi;if(dv=-1|dvdu+wi)dv=du+wi;if(!inqv)Qrear+=v;inqv=true;SPFA算法的优化SLF(Small Label First)SLF(Small Label First)策略：策略：设设队队首首元元素素为为i,i,队队列列中中要要加加入入节节点点j,j,在在djdidjavediave，把，把i i移到队尾。移到队尾。还可以用优先队列代替普通的还

23、可以用优先队列代替普通的还可以用优先队列代替普通的还可以用优先队列代替普通的FIFOFIFO队列队列队列队列 inq inq标志：标志：将要把一个节点入队时。如果一个节点已经在队伍中，将要把一个节点入队时。如果一个节点已经在队伍中，那么不必重复入队。那么不必重复入队。（1 1、节省时间、节省时间 2 2、保证队列长度不超过、保证队列长度不超过n n）判负环时，用栈代替队列，或用迭代加判负环时，用栈代替队列，或用迭代加判负环时，用栈代替队列，或用迭代加判负环时，用栈代替队列，或用迭代加深深深深DFSDFS代替代替代替代替BFSBFS，可以取得明显的优化。，可以取得明显的优化。，可以取得明显的优化

24、。，可以取得明显的优化。例题例题 2.22.2SOJSOJ4243:Saving Girl4243:Saving Girl2012 SCU 2012 SCU 光棍节欢乐赛光棍节欢乐赛光棍节欢乐赛光棍节欢乐赛 题意：有一张地图，经过某点会造成一定的伤害。问题意：有一张地图，经过某点会造成一定的伤害。问初始时最少有多少初始时最少有多少DP值，才能保证不半路阵亡。值，才能保证不半路阵亡。解法：解法：解法：解法：在某个点会获得在某个点会获得在某个点会获得在某个点会获得x x的伤害值，那么就由它向四周的的伤害值，那么就由它向四周的的伤害值，那么就由它向四周的的伤害值，那么就由它向四周的格子各连一条长度为

25、格子各连一条长度为格子各连一条长度为格子各连一条长度为x x的边。求最短路的边。求最短路的边。求最短路的边。求最短路差分约束系统差分约束系统X0=0X0-X1=-1X1-X2=-5X2-X3=-3求X1,X2,X3最小值X1=1,X2=6,X3=9求解差分不等式组有什么好的方法吗？与Bellman-Ford算法对比前面用到过Distv=-wu,v这与前面的不等式约束Xi-Xj=-k很类似，因此可以做如下转化：如果存在约束条件Xi-Xj=-k，则建立一条边由i指向j，权值为k，这样就把差分约束系统问题转化为最短路径问题了，然后利用Bellman-Ford算法求解与Bellman-Ford算法对比

26、差分不等式组可能是没有解的，这实际上就对应了Bellman-Ford求解存在负权回路一般来说，求最小值要用最长路，求最大值要用最短路题意：题意：在区间在区间0,500000,50000上面有一些整数点。上面有一些整数点。现给出现给出5000050000个区间。个区间。并给出每个区间至少应覆盖多少个点。并给出每个区间至少应覆盖多少个点。问这个区间上总共至少有多少个点问这个区间上总共至少有多少个点例题例题例题例题 2.32.3POJPOJ1201:Intervals1201:Intervals解法：如果用数组Si表示在0,i这个区间上面有多少个点，则题中输入数据ai,bi,ci可以表示为Sbi-S

27、ai-1=ci除此之外还有隐含条件：Si+1-Si=0Si+1-Si=1无向图从某点到其它点的最短路径一定会无向图从某点到其它点的最短路径一定会无向图从某点到其它点的最短路径一定会无向图从某点到其它点的最短路径一定会组成一棵最小生成树组成一棵最小生成树组成一棵最小生成树组成一棵最小生成树无向图的生成树，每个点到根节点的路径无向图的生成树，每个点到根节点的路径无向图的生成树，每个点到根节点的路径无向图的生成树，每个点到根节点的路径都是最短路径都是最短路径都是最短路径都是最短路径大家有没有觉得大家有没有觉得大家有没有觉得大家有没有觉得primprimprimprim和和和和dijkstradijk

28、stradijkstradijkstra非常相似？非常相似？非常相似？非常相似？1112证明过程就是证明过程就是证明过程就是证明过程就是求解次小生成求解次小生成求解次小生成求解次小生成树的过程树的过程树的过程树的过程全源最短路全源最短路全源最短路全源最短路Floyd-WarshallFloyd-Warshall算法算法算法算法用法：求无负环图中任两点间的最短路。用法：求无负环图中任两点间的最短路。用法：求无负环图中任两点间的最短路。用法：求无负环图中任两点间的最短路。也可用于求最小环也可用于求最小环也可用于求最小环也可用于求最小环void floyd()for(int k=0;kn;k+)fo

29、r(int i=0;in;i+)for(int j=0;jn;j+)if(disik=-1|diskj=-1)continue;if(disij=-1|disijdisik+diskj)disij=disik+diskj;全源最短路全源最短路全源最短路全源最短路JohnsonJohnson算法算法算法算法JohnsonJohnson算法主要用于求稀疏图上的全源最短路径。算法主要用于求稀疏图上的全源最短路径。算法主要用于求稀疏图上的全源最短路径。算法主要用于求稀疏图上的全源最短路径。其主体思想是利用重赋权值的方法把一个原问题带其主体思想是利用重赋权值的方法把一个原问题带其主体思想是利用重赋权值的

30、方法把一个原问题带其主体思想是利用重赋权值的方法把一个原问题带负权的图转化为权值非负的图。负权的图转化为权值非负的图。负权的图转化为权值非负的图。负权的图转化为权值非负的图。然后再使用然后再使用然后再使用然后再使用 NN次次次次DijkstraDijkstra算法以求出全源最短路。算法以求出全源最短路。算法以求出全源最短路。算法以求出全源最短路。下面先介绍其重赋权值的主体步骤：下面先介绍其重赋权值的主体步骤：下面先介绍其重赋权值的主体步骤：下面先介绍其重赋权值的主体步骤：1.1.增设一点增设一点增设一点增设一点 S S，由，由，由，由 SS往各点连一条权值为往各点连一条权值为往各点连一条权值为

31、往各点连一条权值为 00的边。的边。的边。的边。2.2.使用使用使用使用 SPFASPFA求出求出求出求出 SS到各点到各点到各点到各点 II的最短路径的最短路径的最短路径的最短路径 h(i)h(i)。3.3.对于每条边对于每条边对于每条边对于每条边 w(u,v),w(u,v),将其重赋权为将其重赋权为将其重赋权为将其重赋权为 ww(u,v)=w(u,v)+h(u)-h(v)(u,v)=w(u,v)+h(u)-h(v)。JohnsonJohnsonJohnsonJohnson的重赋权思想的重赋权思想的重赋权思想的重赋权思想也可解决最优调度问题和最小费用流问题也可解决最优调度问题和最小费用流问题

32、也可解决最优调度问题和最小费用流问题也可解决最优调度问题和最小费用流问题点连通度与边连通度在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合割点集合。点连通度点连通度:最小割点集合中的顶点数。如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合割边集合。边连通度边连通度：最小割边集合中的边数。如果一个无向连通图的点连通度大于1，则称该图是点双连通的，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，割点集合的唯一元素被称为割点，又叫关节点。如果一个无向连通图的边连通

33、度大于1，则称该图是边双连通的，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥，又叫关节边。割点与桥割点与桥割点割点割边割边双联通分支：双联通分支：在图G的所有子图G中，如果G是双连通的，则称G为双连通子图。如果一个双连通子图G它不是任何一个双连通子图的真子集，则G为极大双连通子图。双连通分支，或重连通分支，就是图的极大双连通子图。特殊的，点双连通分支又叫做块。去掉任一割边/割点：图被分割成多个联通块去掉所有割边：图被分割成多个双连通分支。（点双联通分支又称为“块”）割点也分割了双联通分支，但是割点是属于双联通分支的。注意：割点同时属于多个双联通分支

34、，割边不属于双联通分支，其它点和边只属于一个双连通分支求割点求割点 原来路线替代路线环。移除一个点之后，经过改点的路线被截断了。要是沒有替代路线，无法绕过该点，就会不联通，该点就形成关节点。反过来说，如果有替代路线，该点就不会形成关节点。要在一张图上找替代路线不太直接，但是找环就比较直接了把图重新画成树的形状，就容易找环了！要把图重新画成树的形状，利用DFS遍历就可以了。任取树上的一个点，当这个点的祖先与每一棵子树想要互通有无，利用父子边的话，显然会经过此点；另一方面，不想利用父子边的话，不想经过此点的话，就必须利用返祖边了。在 DFS树之中，子树与子树之间不会有边，所以只需要考虑祖先与子树之

35、间有没有 返祖边。这也就是说，祖先与每一棵子树之间都有 返祖边 的话，该点就不是关节点；祖先与其中一棵子树之间缺少 返祖边 的话，该点就是关节点。定义DFS(u)为u在搜索树中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。一个顶点u是割点，当且仅当：(1)u为树根，且u有多于一个子树。(2)u不为树根，且满足存在(u,v)为树枝边，使得DFS(u)=Low(v)。一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)Low(v)。Low(u)=min DFS(u)，DFS(v)(u,v)为后向边(返祖边)Low(v

36、)(u,v)为树枝边(父子边)算法步骤：算法步骤：算法步骤：算法步骤：求点双连通分支对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。求边双连通分支只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。例题例题例题例题 3.13.1NJUST 194:TWO NODESNJUS

37、T 194:TWO NODES2013 2013 南京赛区邀请赛南京赛区邀请赛南京赛区邀请赛南京赛区邀请赛题意：给出一个无向图（V,E5000），问去掉两个点之后，这个图最多变成了几个连通块。解法：解法：解法：解法：在求割点的过程中，若在求割点的过程中，若在求割点的过程中，若在求割点的过程中，若dfsdfs树上的某子节点树上的某子节点树上的某子节点树上的某子节点v v的的的的lowv=lowv1,cnt1,则必无满则必无满足条件的点，因为一个出度为足条件的点，因为一个出度为零的点无法到达另一个出度为零的点；若零的点无法到达另一个出度为零的点；若cnt=1,cnt=1,则该点所对应的强联通分量中

38、的点则该点所对应的强联通分量中的点的个数即为答案。的个数即为答案。SATSatisfiability可满足性问题第一个被证明为NP完全的问题2-SAT:(SAT的特殊情况之一)简要步骤：简要步骤：对于每个点i，建立两个节点，i和i,分别对应两个选项。如果选择了i就必须选择j。那么就在连两条边：ij，ji。进行强联通缩点，如果某一对i和i处于同一个联通块中，则无合法方案。输出方案交替染色2-SAT的对称性对称性：i j 则 i j对称传递性：i j k 则 i j k路径的对称性：u v 则 u v倍增法(在线)Tarjan算法(离线)在线与离线在线算法：用比较长的时间作预处理，但是等信息充足以

39、后每次回答询问只需要用比较少的时间离线算法：把所有的询问读入，然后一起把所有的询问回答完成例如：Fibonacci的在线算法复杂度为O(n+q)，离线算法复杂度为O(nlogq)Sparse Table算法简称：ST算法dpij表示区间i,i+2j-1的最小值，则dpi0=aidpij=mindpij-1,dpi+2(j-1)j-1这样可以得到所有的dpijSparse Table算法如果询问区间为s,t，则只需要取k=(int)log2(t-s+1)RMQs,t=mindpsk,dpt-2k+1k这时候预处理的算法复杂度仅为O(nlogn)而回答问题仍然是O(1)的复杂度实际操作的时候，我们

40、不一定用log来计算k，也可以通过二分查找。goij代表i节点向根上的方向跳1j次的祖先 voiddfs(intu)voiddfs(intu)for(intt=0;tmapu.size();t+)for(intt=0;tmapu.size();t+)if(depmaput!=-1)continue;if(depmaput!=-1)continue;intv=maput;intv=maput;depv=depu+1;depv=depu+1;gov0=u;gov0=u;for(intk=1;(1k)=depv;k+)for(intk=1;(1k)depu)swap(u,v);int jmp=dep

41、u-depv;for(int k=16;k=0;k-)if(jmpk&1)u=gouk;if(u=v)return u;int k;for(k=16;k=0;k-)if(1k)depu)&gouk!=govk)u=gouk;v=govk;return gou0;例题例题例题例题 4.14.1HDU 4718HDU 4718：The LCIS on the TreeThe LCIS on the Tree2013 2013 成都赛区邀请赛成都赛区邀请赛成都赛区邀请赛成都赛区邀请赛题意：给出一棵树，每个点有一个权值。给定起点和终点，求两点间路径上，权值的最长连续递增子序列。解法：解法：解法：解法：对于每个对于每个对于每个对于每个LCALCA倍增区间区间维护六个量：倍增区间区间维护六个量：倍增区间区间维护六个量：倍增区间区间维护六个量：最长左对齐递增，最长右对齐递增，最长递增最长左对齐递增，最长右对齐递增，最长递增最长左对齐递增，最长右对齐递增，最长递增最长左对齐递增，最长右对齐递增，最长递增最长左对齐递减，最长右对齐递减，最长递减最长左对齐递减，最长右对齐递减，最长递减最长左对齐递减，最长右对齐递减，最长递减最长左对齐递减，最长右对齐递减，最长递减在求在求在求在求LCALCA过程中合并这些量过程中合并这些量过程中合并这些量过程中合并这些量谢谢！