图论专题选讲

1、图论专题选讲by acerlawsonA - A - 秋实大哥与连锁快餐店秋实大哥与连锁快餐店 题目大意：二维平面上有n个点，部分点是特殊点，添加长度和最小的边，使得任意一点都能至少能和一个特殊点连通。 首先，先解决一个子问题：n个点的完全图中，有m=n(n-1)/2条边，求最小生成树求最小生成树。 对于完全图: prim算法：时间复杂度O(n2)，空间复杂度O(n). Kruskal算法：时间复杂度O(mlogm) ，空间复杂度O(m). 在解决完全图的最小生成树中，prim更优。A - A - 秋实大哥与连锁快餐店秋实大哥与连锁快餐店 题目大意：二维平面上有n个点，部分点是特殊点，添加长度

2、和最小的边，使得任意一点都能至少能和一个特殊点连通。接下来，再考虑第二个子问题：二维平面上的n个点，添加长度和长度和最小的边，使得整体联通整体联通。其实就是第一个子问题的变形，n个点的完全图，任意两个点的边权定义为这两个点之间的欧几里德距离，求最小生成树。A - A - 秋实大哥与连锁快餐店秋实大哥与连锁快餐店 题目大意：二维平面上有n个点，部分点是特殊点，添加长度和最小的边，使得任意一点都能至少能和一个特殊点连通。 最后，我们回到原题，可以发现第二个问题和原题的区别只是特只是特殊点的存在与否殊点的存在与否。那么如何解决特殊点呢？很简单啊！特殊点之间的边权变为0就解决了！A - A - 秋实大

3、哥与连锁快餐店秋实大哥与连锁快餐店 题目大意：二维平面上有n个点，部分点是特殊点，添加长度和最小的边，使得任意一点都能至少能和一个特殊点连通。 如何实现？ 方法1.在更新边权的时候： 如果两个点都是特殊点，d(vi,vj)=0； 否则，d(vi,vj)=欧几里德距离; 方法2.先把特殊点处理了，再把普通点处理了。B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。 （无关紧要的题意补充：保证起点到终点一定可达。 题目来源：Topcoder srm div1 B 首先，最简单的，求起点到每个点i的最短路disti。 Dijkstra,spfa什么的随便选一个乱搞一

4、下就行了。B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。 接下来是重点，求方案数。首先我们总需要知道最短路可以经过哪些点吧？我们可以倒着从终点往回走，通过一个普通的队列来实现。先把终点t扔进空队列，每次那一个点i拿出来。对于点i的所有边edge(i,j)，如果前驱distj=edge(i,j)+disti,那么就可认为：一定能通过j点到达i的最短路disti，同时把j点也加进队列 。直到队列为空为止。B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短

5、路方案数。 这样就能知道所有最短路径中经过的所有可能点有哪些了。然而看上去对求方案数并没有什么卵用。 其实只要在过程中稍稍修改，就可以求出答案了。B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。 对于每个点i，定义两个值ansi和waysi。 ansi表示从这个点i到终点最短路的总方案数。 waysi,表示从这点i到终点最短路中还有waysi的方案数的方案数没有分配给前驱j点（满足distj=edge(i,j)+disti的点）B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。 具体实现过程： 每次从队列中拿队首元素u出来：

6、 遍历所有与它相邻的边e如果diste.v=distu+e.d，那么分配给v:wayse.v+=waysu 遍历完边以后，把waysu分配给自己:ansu+=waysu。 这样waysu就被分配完了，置0。B - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。waysanswaysanswaysanswaysansB - B - 秋实大哥带我飞秋实大哥带我飞 题目大意：非负权无向图中最短路方案数。 接下来是细节问题： 重边：没影响啊！ 0边：从终点往回走的过程中只要遇到0边答案就是无数条啊！ 算法：Spfa的思想求方案数！也可以用其他方法乱搞：拓扑排序、dfs之类

7、等等。C - C - 秋实大哥与时空漫游秋实大哥与时空漫游给定初始的时间St和地点Sp，现在要求求出一组合法路径使得，能够在Tt时间之前到达Pt。每一条边（传送门）定义：起点a,终点b,起始时间c,终点时间d。如果想走这条边，那么就必须在c时刻之前到达a，等候到c时刻的时候通过该边到达b点的d时间。题意很复杂？没有头绪？其实很简单！其实很简单！C - C - 秋实大哥与时空漫游秋实大哥与时空漫游首先，每条边走一次就够了。走两次反而会致使一个星球上同时存在两个秋实大哥。接下来，我们定义对每个点定义数组timi表示目前为止最早能到表示目前为止最早能到i点的时刻点的时刻。显而易见，对于起点，timS

8、p=St，对于其他点，timi=infC - C - 秋实大哥与时空漫游秋实大哥与时空漫游然后，对于每个点i，我们对所有边起点边起点为i的按出发时间出发时间c从大到小排序。这部预处理的时间复杂度最多是mlogm。这样排序是有目的性的：对于点i的每个出边e，如果这个边e能走，那么排在它前面的边都可以走。C - C - 秋实大哥与时空漫游秋实大哥与时空漫游最后，我们O(m)的时间复杂度求出答案。这也就是为什么边数敢放5*105的原因。对于每个点i在定义一个zzi=0，表示现在已经访问完了zzi-1号边，准备访问zzi边节点。定义个一个队列Q，开始时把起点加入队列。每次取队首元素x出来，从第zzx条边e开始向其他点的time.b更新，（time.d?）如果更新成功，将e.b入队。直到遇到某条边的c要小于timx。直到队列为空为止，做完了。C - C - 秋实大哥与时空漫游秋实大哥与时空漫游C - C - 秋实大哥与时空漫游秋实大哥与时空漫游最后只需要判断最后只需要判断timTp=Tt