第一章选择题30分1.8hash表和二叉搜索树

1、NGYN 表和二叉搜索树对于图论基本算法，NOIP 初赛不要求会实现算法，但手工操作还是要会的（NOIP2008 提高组初赛填空题第一题），复赛是要求会代码实现的。本节学习方法每个算法看完 flash 后，都要制造简单数据手工模拟一遍。并且要对比各个算法的异同和细节。一、求最小生成树的 Kruskal 算法最小生成树算法的目标：一个 n 个点的图，选若干条边（一定是 n-1 条）使得图连在一起，并且所有选中的边的长度和最小。学习步骤：1、flash 地址htt/fine/resour/FlashContent.as=1042、算法描述给出一个 n 个点的连通图，每次选剩下最小的边，保证和已选的

2、边不环，否则选第二小边，如果2、源程序喜欢选第三小，直到选足 n-1 条边。自己的同学，尝试自己写代码，然后调试通过后，对照标准代码。也可以去 ac POJ、 89、2349二、求最小生成树的 prim 算法和 Kruskal 算法一样的功能，各有优点。学习步骤：1、flash 地址htt/fine/resour/FlashContent.as=1032、算法描述给出一个 n 个点的连通图，首先选中一个点（一般为第一个点），每次选和已选中的所有点相连的边中最小一条（该边两个端点必须一个是已选中点，另外一个为还没选的点）。2、源程序同 Kruskal。在这里给出作者的 prim 算法，主要为了对

3、比下面将要学习的最短路 Dijkstra 算法。/poj1258 的代码/以下注释中，已选中的点为“”，这样说constoo=99999999; vara:array1.100,1.100of long;/ 图（邻接矩阵）中的点和非的点比较清晰。d:array1.100of longbo:array1.100of;/d9表示结点 9 到“”的距离。;/ bo9=true 就表示点 9 是的人，若bo9=false 那么点 9 就不是的人了。n,i,j,k,p,min,sum:long beginwhile not eof do beginread(n);for i:=1 to n do for

4、 j:=1 to n do read(ai,j);fillchar(izeof(bo),false);for i:=1 to n do di:=oo;d1:=0;/一开始谁都不是sum:=0;的人，点 1 到的距离为 0，等下首先选 1盟for k:=1 to n dobegin/每次选一个到距离最小的点/第一步：选点(找那些还没有被找过，而且目前最小的点） min:=99999999;for i:=1 to n doif (not boi) and (mindi) then /选距离最小的点，前提是这个点它还没盟begin有加min:=di; /最小值点p:=i;/end;sum:=sum+

5、dp;/累加新的边/第二步：调整（调整那些没有被找过的点）bop:=true;for i:=1 to n do/ f 标记p 已经是属于的了。以后不需要再选了。/ 这是调整！ p 作为刚加盟的点，需要做贡献的。if (not boi)and(diap,i) thendi:=ap,i;end;wrin(sum);end;end.三、求单源最短路径 Dijkstra 算法单源最短路径算法的目标：一个 n 个点的图，假定出发点 st，要求点 st 到其他点的最短的路径长度。Dijkstra 算法可以解决一源点对多目标点的最短路问题（当然也可以解决一对一的最短路问题）学习步骤1、flash 地址htt

6、/fine/resour/FlashContent.as=1052、算法描述类似 prim 算法，给出一个 n 个点的连通图，假设出发点为 st，那么 dst=0,di表示点 i 到出发点的距离（i 表示除了出发点外的任意点）。每次选 d值最小的点 p，然后点 p 去更新其他还没有被选中的点 i 的 d值。3、源程序/poj1847 的代码const oo=100000000; vara:array1.210,1.210of long;d:array1.210of long; /d9不是点 9 到的距离，而是到出发点 1 的距离了。bo:array1.210of;t,n,m,i,j,k,x,y

7、, beginread(t);,minn:long;while t0 do begin dec(t); read(n,m);for i:=1 to n do for j:=1 to n do ai,j:=oo; for i:=1 to m do beginread(x,y,cc);if ccdi) then begin minn:=di; p:=i;end;if minn=100000000 then break;/第二步：调整（调整那些没有被找过的点） bop:=true;for i:=1 to n doif (not boi) and( dp+ap,idi) thendi:=dp+ap,i

8、;/就是这里和 prim 不一样end;if dn=100000000 then wrin(-1) else wrin(dn);end;end.四、拓扑排序算法拓扑排序算法的目标：一个 n 个点的图，假定出发点 st，要求点 st 到其他点的最短的路径长度。Dijkstra 算法可以解决一源点对多目标点的最短路问题（当然也可以解决一对一的最短路问题）学习步骤1、flash 地址htt/fine/resour/FlashContent.as=1072、算法描述给出一个 n 个点的有向连通图，首先统计好每个点的前驱个数，每次一个前驱个数为 0 的点 p，并且所有前驱为 p 的点的前驱个数减一。3、

9、源程序比较/Poj2367 代码const max=110; var自己看完 flash 后尝试去实现拓扑排序的代码。map:array1.max,1.maxof;s:array1.maxof long a:array1.maxof long bo:array1.maxof n,k,i,j,x,y,p:long;begin;/si表示点 i 的前驱结点的个数;/ 用在保存输出的; /标记是否已经被选过了。read(n);/这个图有 n 个点/图论的题目初始化很重要fillchar(map,sizeof(map),false); fillchar(s,sizeof(s),0);fillchar(

10、izeof(bo),false);for i:=1 to n do beginread(x);/表示第 i 个点有 k 个后继While(x0) do beginmapi,x:=true;/ i 到 x 之间要连一条有向边 inc(sx);/x 的前继结点数目加一个 read(x);end;end;bk:=true;/假设拓扑的过程是顺利的for k:=1 to n dobegin/ 每次选出一个点。/第一步工作：找点 p:=0;for i:=1 to n do/找一个没有被选过，而且目前没有“前驱累赘-si=0的点if (not boi)and(si=0) then begin p:=i;break;end;ak:=p;/ 说明点 p 是第k 个选出来的/第二步工作：调整bop:=true;/ 标记该点已经找过了，以后不要再找它了for i:=1 to n do/ 作为新选中的点，p 还是要进行调整的啊！if (not boi)and (mapp,i=true) then dec(si);/怎么调整？所有点 p 的直接后继点 p-i，全部 si减一。end;/输出for i:=1 to n-1 do