浙江林学院ACM集训队阶段总结.pptVIP

浙江林学院ACM集训队阶段总结 Write by Zhuangli(zjfc3) 图论What is that? 什么是图论? 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若 干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系 。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。 并查集及其拓展 并查集是一种信息内聚很强的数据结构，它在判定图的连通性以及等价类划分的时空效率上有着不可替代的优势。但并查集的特殊应用也应该有所了解. 以下两类是并查集在实际问题中的特殊拓展，希望大家能够进行快速掌握. 1.集合计数问题 2.二分图识别 集合计数问题 HDU 1856 More is better 题意： 若A与B认识，B与C认识，则A与C认识，现给你一组人员的关系表，求在这样的不同群组内，拥有最多人数群组的人数。 集合计数问题 有什么想法？ 并查后统计并查数组? 不可行 数据范如果逐个统计必定TLE 不能如此暴力…. 思路如何……想3分钟 集合计数问题 联想到并查集的构造原理 构造rank数组,在并操作中入手！！ 好,问题解决!! 二分图识别 HDU 1829 A Bug Of Life 题意： 假定两只飞虫(Bug)关系表，如A B表示A仰慕B，问是否存在同性的飞虫互相仰慕（也就是同性恋问题）. 二分图识别 难点：A与B的集合归属不定 如何解决?思考！！！ 二分图识别 非此即彼思想的运用 构造数组opp，初始化为本身编号，若A与B有关，首先进行find(A),find(B)的操作，若根相同，则说明A与B属于同一集合，即同性恋，否则执行下面的操作，如果A的opp等于本身，说明A的opp未初始化，使之等于B，否则将A的opp与B进行Unition操作，类似的如果B的opp等于本身，说明B的opp未初始化，使之等于A，否则将B的opp与A进行Unition操作 二分图识别 想想为什么？ 二分图的性质决定 更深入的二分识别……(如统计最小单元集，如何进行 _ 课后思考!) 最短路径问题 在一个网络图中求解一点到另一点间最短距离及其路径的算法称之为最短路径问题。 1、单源正权最短路径 2、单源带负权最短路径 3、多源最短路径 单源正权最短路径 求解单源最短路径的Dijkstra算法，状态转移与贪心准则的完美结合。 思想：动态规划 策略：贪心( O(Ve) ) 步骤： 1.构造辅助数组Dis[],Vist[],Dis[i]表示从源点出发到达i点的最短距离,Vist[i]表示i点是否已被访问，算法开始执行时令所有Dis[i]=w(start,i)[不可达为MAX],Vist[start]=true. 2.每次得到Dis[]数组中最小且未被访问过的点i，标记Vist[i]=true,遍历所有与i相关的边，若得到Dis[i]+w(i,j)Dis[j]，则更新Dis[j]=Dis[i]+w(i ,j). 3.如此循环直到所有点均被标记. 单源正权最短路径 Dijkstra的致命弱点：不能处理带负权的边 思考：Why? 问题出自贪心策略！！若存在负权，则算法将不断更新负权边相关顶点的Dis值，从而导致答案错误! 单源带负权最短路径 如何处理Dijkstra的遗留问题？ 摈弃贪心策略 执行松弛技术-----Bellman-ford算法 单源带负权最短路径 什么是松弛技术？ 日常生活中的例子~~（1+1猜想） 松弛技术的本质是首先给予一个物体很高的估价，在每次的迭代中对估价进行修正，在有限次的迭代后使估价与实际值吻合的技术。 单源带负权最短路径 思想：若存在N个点的网络，则对于起点到终点最多经过N-1条边 策略：有限迭代下的松弛技术 单源带负权最短路径 步骤： 1、开辟辅助数组Dis[],记录源点到点i的最小距离，初始时设所有Dis[]值为MAX，Dis[start]=0. 2、进行n-1次迭代，对于所有边，若满足Dis[i]MAXDis[i]+w(i,j)Dis[j],更新Dis[j]= Dis[i]+w(i,j). 3、执行完成后，再执行1次迭代，若出现Dis[i]+w(i,j)Dis[j]的情况，则表明出现了负环，此时不存在最短路径，否则Dis[end]即所求单源最短路径. 单源带负权最短路径 算法分析： 1、迭代v-1次，每次遍历所有边,复杂度O（VE）,E为全部边，Dij