图论模型的建立与应用ppt课件.ppt

《图论模型的建立与应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论模型的建立与应用胜利一中孙猛图论的一些基本算法最短路：FloyedDijkstraSPFABellman_Ford最小生成树PrimKruskal拓扑排序阿狸和桃子的游戏2012国家集训队题目大意一个带权图G，有n（n为偶数）个点，m条边，点和边都有权值。两个人依次选点，每次选一个，选完后每个人得到了一个由n/2个点组成的点集。问先选的人比后选的人最多能多得多少分得分计算方法：对于点集S算法其实这是一道水题……因为这题问的是差值，所以我们不需要知道具体的得分我们只需要将每条边的权值平均加到两个点上，然后将点按权值排

2、序，然后贪心选就行了。对于一条边，如果两个点被一个人选走，那么这个人得到了这个边权，如果两个点各被一个人选走，那么他们各得到一半权值，差值为0NOIP2009最优贸易题目大意N座城市，M条有向道路，有一种商品，在每一座城市中的价格分别为w[i]。你要从城市1走到城市n，你可以在经过的任意一座城市买入它，然后在随后经过的任意一座城市卖出，你最多能赚多少钱？数据范围1≤n≤100000,1≤m≤500000,1≤w[i]≤100算法用类似SPFA的算法，求出1到每个点路径中所能经过的最低的价格a[i]和每个点到n的路径中所

3、能经过的最高的价格b[i]。Ans=max(b[i]-a[i])[Usaco2008Oct]灌水FarmerJohn已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0).计算FarmerJohn所需的最少代价。算法如果只能建造一个水库，那么这就是一个最小生成树问题现在可以建造多个水库，那么最

4、后就应该是多棵最小生成树我们可以增加一个点T，每个点都向T连一条边，边权为在该点修水库的费用，然后做一遍最小生成树就得到了答案求S到T的一条路径，使路径上的各边权值的乘积最大。N<=10000,M<=100000算法：ln(w1*w2*w3*...)=ln(w1)+ln(w2)+ln(w3)...我们可以将每条边的边权取对数，然后求出S到T的最短路长度L，那么Ans=eL最优比率生成树给定一个无向图，每条边有两种边权wi1，wi2，求一棵生成树，令sum(wi1)/sum(wi2)最大。算法：我们设最后的答案为ans，

5、那么原图的任意一棵生成树都满足sum(wi1)/sum(wi2)<=ans将上式变型sum(wi1)<=ans*sum(wi2)ans*sum(wi2)-sum(wi1)>=0sum(wi2*ans-wi1)>=0那么我们可以二分答案k，将边权变为wi2*ans-wi1，对于所有小于0的边，如果存在一棵生成树，那么说明k比ans小，往上二分，否则往下二分。糖果幼儿园里有N个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果，并且满足小朋友们所有的要求。输入的第一行是两个整数N，K。接下来K行，表示这

6、些点需要满足的关系，每行3个数字，X，A，B。如果X=1，表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；如果X=2，表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；如果X=3，表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；如果X=4，表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；如果X=5，表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；N<=100000，K<=100000，1<=X<=5，1<=A,B<=N差分约束系统本题是一个差分约束系统的问题求解差

7、分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。我们以最长路径为例。用f[i]表示第i个小朋友最少需要的糖果，如果输入2ab，那么需要f[a]

8、设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(iinA,jinB)，则称图G为一个二分图。二分图匹配给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。匈牙利算法对A中每个点进