数据结构精品课件-并查集.pptVIP

Parity(ceoi99) 有一个01序列,长度=1000000000,现在有n条信息,每条信息的形式是－a b even/odd。表示第a位到第b位元素之间的元素总和是偶数/奇数。 你的任务是对于这些给定的信息，输出第一个不正确的信息所在位置-1。信息的数目不超过5000。 如果信息全部正确，即可以找到一个满足要求的01序列，那么输出n。 Parity(ceoi99) 输入文件 第一行一个整数m表示01序列的长度，第二行一个整数n表示信息的数目。 接下来是n条信息 样例输入 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 样例输出 3{因为第4个信息是不正确的，所以输出3，表示从1到3条信息都是正确的} Parity(ceoi99) 从整个01序列肯定是无法入手的，因为它的长度高达109。 从范围比较小的n入手。也就是说我们需要对信息进行一些特殊的处理。 a b even/odd，那么将元素b指向a-1，边的权值是even/odd。 下面我们由样例来说明一下这个处理方法。 Parity(ceoi99) 0 4 2 6 1 2 even 3 4 odd 5 6 even 1 6 even 0 1 0 0??? Parity(ceoi99) 显然在第4条信息加入的时候，6到0已经有值存在，即(0+1+0)mod 2=1，这时添入6到0为0显然是不对。 实现的时候不用开1-109的数组，因为出现的不同元素最多有104而已，因此，开一个列表存储元素即可。 算法的大致框架就是对于读入的信息不断地用上述方法处理，由区间的递推性质可以得出矛盾与否。 上述算法的实现就用到了并查集。 Disjoint Sets小结 先从问题的简单做法入手，构造出原始模型。 如果原始模型是对于集合之间合并处理问题，那么就可以使用并查集使得程序变得高效。 并查集的路径压缩只有在元素之间的特性存在递推关系时才可以使用。 练习1 用并查集实现kruskal算法的优化 Kruskal的原始算法是－对于所给边进行排序，然后从小到大往图里加边：如果某条边的左右结点分别属于不同的两个集合(即两个点还没有连通)，那么就加入这条边，否则处理下一条边。 练习2－极品飞车 FC星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时FC星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),但FC星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。 练习2－极品飞车 输入格式：第一行有2个正整数n (1n201)和m (m1001),表示有N个城市和M条SARS。接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speed的SARS。然后是一个正整数Q（Q11),表示寻路的个数。接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。 输出格式：每个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。 练习2－极品飞车 Sample Input: 4 4 1 2 2 2 3 4 1 4 1 3 4 2 2 1 3 1 2 Sample Output: 1 0 练习2－极品飞车 首先枚举速度最大的那条边，然后把速度大于这条边的边都删掉，接下来的任务就是在残图中寻找一条路，路上的最小的那条边要尽量大。这个地方用并查集实现，对于剩下的边由大到小排序，然后逐个往集合里面加，直到某次加入操作后起点和终点被加到了同一个集合，这时停止操作，刚才加的那条边就是一条所求的最小边最大的。算法复杂度m^2。 * 并查集初步 并查集的引入 实际中经常用到一组互不相交的子集，并且经常需要对其进行如下两个操作： 确定一个元素所在的子集 合并两个子集 路径压缩 于是人们提出了一个抽象数据类型并查集。 可以用多种方法实现集合，如位向量、有序表等，根据并查集操作的特点，在此采用树结构表示集合。 树中每个结点对应集合中的一个元素，为操作方便，树的每个结点中含有一个指向双亲的指针，并约定用根结点代表这个集合。 并查集的抽象数据类型定义 ADT MFSet { 数据对象： 假设集合S有n个元素，每个元素属于同一个数据对象。S0，S1，…，Sm-1是S的m个子集， SS是以S0，S1，…，Sm-1为元素构成的集合。 数据关系：S0∪S1∪…∪Sm-1=S，S0