图论与有哪些信誉好的足球投注网站在noip中的应用PPT.ppt

应用范围：稀疏图，用数组模拟邻接表会爆内存的图。 存储与遍历： 遍历： Procedure dfs(x:longint); begin For i:=1 to len(x) do begin top:=head[x]; now:=top+i-1; Point:=c[now]; Dfs（now）； end; 存储： Begin Readln(m); For i:=1 to m do begin Readln(x,y); r[i]:=x;c[i]:=y;end; Qsort(r[i],1,m]); For i:=1 to m do begin Temp:=r[i]; If tempr[i-1] then head[temp]:=I; inc(len[temp]);end; End; 一种特殊的前向星——链式前向星（相见资料） （三）.广搜及其应用 广度爆搜 图的广度优先遍历（FLOODFILL ) 单元最短路（spfa, Dijkstra ） 最小生成树（prim） 广搜染色（二分图的检验） 广度爆搜 细胞（cell） 【问题描述】一个矩形阵列由数字0~9组成，数字1~9代表细胞，细胞的定义是沿细胞数字上下左右如果还是细胞数字则为同一细胞，求给定矩阵阵列的细胞个数。 【输入格式】第一行为整数m，n，接着m行，每行n个数字 【输出格式】细胞的个数 【输入样例】 cell.in 4 10 0234500067 1034560500 2045600671 0000000089 【输出样例】 cell.out 4 传说中的Floodfill procedure flood_fill(x,y:longint); begin if (x=0) or (y=0) or (x=n) or (y=m) or not v[x,y] then exit; //超出了边界或者已经到过 v[x,y]:=false; //标记为已经到过 flood_fill(x+1,y);//下 flood_fill(x-1,y); //上 flood_fill(x,y+1); //右 flood_fill(x,y-1); //左 end; Spfa 我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 procedure spfa; begin fillchar(q,sizeof(q),0); h:=0; t:=0;//队列 fillchar(v,sizeof(v),false);//v[i]判断i是否在队列中 for i:=1 to n do dist[i]:=maxint;//初始化最小值 ? inc(t); q[t]:=1; v[1]:=true; dist[1]:=0;//这里把1作为源点 ? while ht do begin h:=(h mod n)+1; x:=q[h]; v[x]:=false; for i:=1 to n do if (cost[x,i]0) and (dist[x]+cost[x,i]dist[i]) then begin dist[i]:=dist[x]+cost[x,i]; if not(v[i]) then begin t:=(t mod n)+1; q[t]:=i; v[i]:=true; end; end; end; end; Spfa代码 Noip2009原题：最优贸易 C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1 条。C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设C 国n 个城市的标号从1~ n，阿龙决定从1 号城市出发，并最终在n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并