ACM培训——图论(一)

图论（一）四川大学ACM/ICPC集训队李冠一2013.7百度百科：图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。个人理解：图论是ACM/ICPC中经常出现的一类题目。多见于中档题，当然也有神题神模型。图论相对好入门，图的BFS/DFS遍历几乎一个没有算法基础的人也可以掌握。但是，当研究深入之后，实际上图论包含着许多艰深而复杂的理论。当然，对于大多数普通的ACMer来说，我们首先要做的就是熟悉基本算法、掌握常见模型、提高建模思维。一、图的BFS遍历算法步骤：1、用dis[]数组表示各点距离起点S的距离。dis[i]=-1表示i点还未被访问。用map[i][j]表示i点和j点之间是否有边。2、将dis[s]初始化为0，将其它点的dis初始化为-1。将S点入队3、while（队列非空）{从队首出队一个元素u{对于所有跟u有边相连的点v:if(dis[v]==-1){dis[v]=dis[u]+1;v入队}}}•每个节点只会入队一次，也只会出队一次。•时间复杂度O(V+E)。基本性质：•队列中的节点距起点的最短距离单调递增。•且队首与队尾的最短距离差值不超过11-2边权图的BFS：把每条长度为2的边中间加一个点，拆成两条边例题1.1HDOJ1180:诡异的楼梯题意：在一个地图上，有一些位置是空地，有些位置有障碍。还有一些位置有梯子，不过梯子的方向有的是横向，有的是竖向，且方向每分钟变化一次。求从起点到终点的最短时间。解法：每次最多有五种状态可以选择：上、下、左、右、停留原地等待。设计状态时除了要保存距离以外，还要保存当前的时间是奇数还是偶数这样才能在BFS时进行状态的转移二、图的DFS遍历算法步骤（以0-1边权图为例）：1、从某个节点开始，每次任选一个与它相邻的未访问节点访问下去2、直到当前节点的所有相邻节点都已经被访问过。3、回溯到第一个未被访问过的节点三、拓扑排序•概念引入：一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。算法步骤1.从有向图中选取一个没有前驱的顶点，并输出；2.从有向图中删去此顶点以及所有以它为尾的边；3.重复上述两步，直至图空。*如果图不空，但找不到无前驱的顶点，说明图中有环。拓扑序列：v6,v1,v4,v3,v2,v5注意：拓扑序列可能不唯一拓扑排序的应用•判断一个有向图中是否有环。无环的图所有点都能进行拓扑排序。•求DAG图最长路•类似于课程安排问题的题目最小生成树定义bchifaedg48812414791067211生成树：对于一个无向图，生成树是它的一个无回路的联通子图最小生成树：各边权值和最小的生成树有向图的最小有向生成树？——最小树形图最小生成树•prim算法(复杂度O(n^2))•kruskal算法(复杂度O(m*lg(m))Prim算法•贪心准则–加入后仍形成树，且耗费最小–始终保持树的结构——Kruskal算法是森林•算法过程–从单一顶点的树T开始–不断加入耗费最小的边(u,v)，使T∪{(u,v)}仍为树——u、v中有一个已经在T中，另一个不在T中Prim算法过程bchifaedg488414791067211aidcbhgfe12Krustal算法•kruskal算法思想：贪心选取最短的边来组成一棵最小的生成树。•具体做法：先将所有的边做排序，然后利用并查集作判断来优先选择较小的边，直到建成一棵生成树。intkruskal(){intans=0;sort(edge.begin(),edge.end());for(inti=0;iedge.begin();i++){if(reunion(edge.u,edge.v)){ans+=edge.w;}}returnans;}代码如下：intfindp(intx){returnp[x]==-1?x:p[x]=findp(p[x]);}boolreunion(intx,inty){intpx=findp(x);intpy=findp(y);if(px==py){returnfalse;}p[px]=py;returntrue;}Prim和Kruskal的区别Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边：对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kruskal,其选取的边(u,v)任意，只要这个边的加入不能使被覆盖的顶点构成回路。生成树计数对于有n个点的图，构造一个矩阵，使得：若i==j，a[i][j]=dex[i]。（dex[i]为节点i的度数）。否则，若点i和点j间有边相连，a[i][j]=-1。若无边相连，a[i][j]=0。然后求这个矩阵的行列式，得到的即是这个图的生成树个数。有带权图G,对于图中每条边e[i],都有benifit[i](收入)和cost[i](花费),我们要求的是一棵生成树T,它使得∑(benifit[i])/∑(cost[i]),i∈T最大(或最小).解法：二分or迭代根的度数不超过K的最小生成树。解法：迭代最优比率生成树解法：0-1分数规划设x[i]等于1或0,表示边e[i]是否属于生成树.则比率r=∑(benifit[i]*x[i])/∑(cost[i]*x[i]),0≤im.令：z=∑(benifit[i]*x[i])-l*∑(cost[i]*x[i])两个性质:1.z单调递减证明:因为cost为正数,所以z随l的减小而增大.2.z(max(r))=0证明:若z(max(r))0,∑(benifit[i]*x[i])-max(r)*∑(cost[i]*x[i])0,可化为max(r)max(r).矛盾;若z(max(r))=0,根据性质1,当z=0时r最大.单源最短路径问题•单源最短路径=SingleSourceShortestPath，即在有向图（或无向图）中求解给定点到其他点之间的最短距离算法：•DFS算法•Dijkstra算法•Bellman-Ford算法•SPFA算法用优先队列（二叉堆）优化dijkstra算法5、重复4、5直至所有的点都进入S1、集合S，表示已经找到最短路径的点。dis[]表示各点当前据源点的最短距离2、初始时，集合中只有源点。3、每个点u进入集合S时，用dis[u]+map[u][v]更新所有与它相连的节点v的dis[v]。4、选取S外的点中dis[]最小的一个点进入S237184566134105275934682演示：求从1到8的最短路径237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{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,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,4,6}min{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,7}min{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=6237184566134105275934682X={1,2,4,6,7}min{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,7}min{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=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10voiddijkstra(ints,intt){d[s]=0;q.push(make_pair(s,0));while(!q.empty()){intu=q.top().first;inttemp=q.top().second;q.pop();if(temp!=d[u]){continue;}for(inti=head[u];i!=-1;i=nxt[i]){intv=to[i];if(d[v]==-1||d[v]d[u]+w[i]){d[v]=d[u]+w[i];q.push(make_pair(v,d[v]));}}}}例题2.1POJ3463:Sightseeing题意：求最短路的种数，及比最短路长度长1的路的总数解法一：dijkstra时不止要记录最短路长度，还要记录最短路的种数，及比最短路长度少1的路的总数。每把一个点加入集合，更新dis[v]的时候就要进行转移。当然，如果dis[v]发生了变化。那么之前的计数要清零。解法二：预处理起点和终点到每个点的最短距离。比最短路长1的点，必定有且只有一条边不在最短路上。枚举。那么，第K短路如何求呢？•先预处理出终点到每个点的距离，作为启发函数。•A*搜索时第k个被搜索到的节点的距离值即是第K短路的值Dijkstra算法的局限性•如果边权为负值，Dijkstra算法还正确吗？•求解右图A至其他点的最短距离•算法步骤：1）标记点A2）Dist[C]=2最小，标记点C3）Dist[B]=3最小，标记点B结束•但是ShortestDist[C]=1ABC23-2Dijkstra算法的局限性•下图中，A至F的最短路径长度是多少？ABCDEF11-1-1-1-1-∞产生错误结果的原因•Dijkstra的缺陷就在于它不能处理负权回路：Dijkstra对于标记过的点就不再进行更新了，所以即使有负权导致最短距离的改变也不会重新计算已经计算过的结果•我们需要新的算法——Bellman-FordBellman-Ford算法思想•Bellman-Ford算法基于动态规划，反复用已有的边来更新最短距离•Bellman-Ford算法的核心思想——松弛•Dist[u]和Dist[v]应当满足一个关系，即Dist[v]=Dist[u]+w[u,v]Bellman-Ford算法流程•所有点i赋初值Dist[i]=+∞，出发点为s，Dist[s]=0•fork=1ton-1for每条边(u,v)如果d[u]!=+∞且d[v]d[u]+w[u,v]则d[v]=d[u]+w[u,v]•for每条边(u,v)如果d[u]!=+∞且d[v]d[u]+w[u,v]则存在负权回路•如果没有负权回路，那么任意两点间的最短路径至多经过n-2个点，因此经过n