图论算法课件.ppt

并查集 并查集的实质就是集合，这个集合是一棵有着树的形式的集合。它支持两种操作：查找某个元素所在的集合，以及将两个集合合并。在并查集的定义中，我们设一个数组fa[1..n]，fa[i]表示第i个元素的父结点。集合的根节点i的fa[i]设为0。查找操作就是顺着fa数组往上找到根结点，合并操作就是就一个集合的根结点的父结点设成另一个集合的根结点。 最短路径 在带权图G=(V,E)中，若顶点vi,vj是图G的两个顶点，从顶点vi到vj的路径长度定义为路径上的各条边的权值之和。从顶点vi到vj可能有多条路径，其中路径长度最小的一条路径成为顶点vi到vj的最短路径。一般有两类最短路径问题：一类是求从某个顶点到其他顶点的最短路径；另一类是求图中每一对顶点间的最短路径。 最短路径 单源最短路径： Dijkstra算法 SPFA算法 多源最短路径： Floyed算法 单源最短路径 Dijkstra算法 用一个dist数组来表示源点S到各个顶点的距离估价。初始时将所有dist[i]设为INTMAX，只有dist[S]设为0，并将S设成访问过。然后不断从未访问的顶点中选出一个dist估价最小的顶点i，将i设成访问过，并从顶点i出发进行松弛操作。这里的松弛操作，是对其他没访问过的顶点j，如果dist[i]+a[i,j]dist[j]就令dist[j]=dist[i]+a[i,j]，即尝试着用i去减小j的距离估价dist，直到最终距离估价变成真实的最短路径。此时所有顶点都应当是已访问过的。 单源最短路径 SPFA算法 需要一个队列作为辅助。用一个dist数组来表示源点S到各个顶点的距离估价。初始时将所有dist[i]设为INTMAX，只有dist[S]设为0，并将S加入队列。然后每次取出队头元素，用它去对其他顶点进行松弛操作，如果对顶点i松弛操作成功，且i不在队列里面，就把它加入队尾。由于一个顶点可能多次入队，需要使用循环队列。直到队列为空算法结束。 多源最短路径 Floyed算法： 设数组a为图的邻接矩阵，而且我们已读入了图的边信息，我们可以直接对a数组进行Floyed算法。 for k:=1 to n do for i:=1 to n do for j:=1 to n do if a[i,k]+a[k,j]a[i,j] then a[i,j]:=a[i,k]+a[k,j]; 这个算法的实质是一个动态规划，不过我们也没有必要究其本源，会用就行。 差分约束系统 为了便于大家理解差分约束系统是什么意思，我们先看一道题目。 【例题】工程规划 造一幢大楼是一项艰巨的工程，它是由N个子任务构成的，给他们分别编号1,2,...,N(5=N=1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1,T2,---,TN并不是很容易确定的。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。 这种要求就可以用M(5=M=5000)个不等式来表示，不等式形如Ti-Tj=B代表i和j的起始时间必须满足的条件。每个不等式的右边都是一个常数B，这些常数可能不相同，但是他们都在区间(-100,100)内。 【例题】工程规划 你的任务就是写一个程序，当给定像上面那样的不等式后，找出一种可能的起始时间序列T1,T2,...,TN，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T1,T2,...,TN中至少有一个为0。 输入：输入文件名为work.in，第一行是用空格隔开的两个正整数N和M，下面的M行每行有三个用空格隔开的整数i,j,B对应着不等式Ti-Tj=B。 输出：输出文件名work.out，如果有可行的方案，那么输出N行，每行都有一个非负整数且至少有一个为0，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息NO SOLUTION。 【例题】工程规划 两个样例： work.in 5 8 1 2 0 1 5 -1 2 5 1 3 1 5 4 1 4 4 3 -1 5 3 -3 5 4 -3 work.out 0 2 5 4 1 work.in 5 5 1 2 -3 1 5 -1 2 5 -1 5 1 -5 4 1 4 work.out NO SOLUTION 题目分析 本题是使用“差分约束系统”解决的。题目让我们对一系列形如Ti-Tj=B的不等式求出一组可行解。如果将Ti-Tj=B变形可得Ti=Tj+B，他让我们联想到了一个东西，那就是松弛操作。我们可以将其转化成一个最短路问题，对于不等式T