高考考完了，把那篇不完整的基本算法的正式稿给大家，这是我准备noip2002时收集多方资料整理而成的。


第三章 基本算法模块

一、数论算法
1．求两数的最大公约数
function  gcd(a,b:integer):integer;
  begin
    if b=0 then gcd:=a
      else gcd:=gcd (b,a mod b);
  end ;

2．求两数的最小公倍数
function  lcm(a,b:integer):integer;
  begin
    if a<b then swap(a,b);
    lcm:=a;
    while lcm mod b>0 do inc(lcm,a);
  end;

3．素数的求法
A.小范围内判断一个数是否为质数：
  function prime (n: integer): Boolean;
    var I: integer;
    begin
      for I:=2 to trunc(sqrt(n)) do
        if n mod I=0 then begin
   prime:=false; exit;
end;
      prime:=true;
    end;

B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
    procedure getprime;
      var
        i,j:longint;
        p:array[1..50000] of boolean;
       begin
         fillchar(p,sizeof(p),true);
  p[1]:=false;
  i:=2;
  while i<50000 do begin
    if p then begin
      j:=i*2;
      while j<50000 do begin
        p[j]:=false;
        inc(j,i);
      end;
     end;
     inc(i);
   end;
   l:=0;
   for i:=1 to 50000 do
     if p then begin
       inc(l);pr[l]:=i;
    end;
end;{getprime}
    
     function prime(x:longint):integer;
       var i:integer;
       begin
         prime:=false;
  for i:=1 to l do
    if pr>=x then break
      else if x mod pr=0 then exit;
  prime:=true;
       end;{prime}


二、图论算法
1．最小生成树
  A.Prim算法：
     procedure prim(v0:integer);
       var
         lowcost,closest:array[1..maxn] of integer;
  i,j,k,min:integer;
       begin
         for i:=1 to n do begin
    lowcost:=cost[v0,i];
    closest:=v0;
   end;
  for i:=1 to n-1 do begin
    {寻找离生成树最近的未加入顶点k}
    min:=maxlongint;
    for j:=1 to n do
      if (lowcost[j]<min) and (lowcost[j]<>0) then begin
        min:=lowcost[j];
        k:=j;
      end;
    lowcost[k]:=0; {将顶点k加入生成树}
       {生成树中增加一条新的边k到closest[k]}
    {修正各点的lowcost和closest值}
    for j:=1 to n do
      if  cost[k,j]<lwocost[j] then begin
        lowcost[j]:=cost[k,j];
        closest[j]:=k;
      end;
    end;
end;{prim}

B.Kruskal算法：(贪心)
  按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点v所在的集合}
  var i:integer;
  begin
    i:=1;
    while (i<=n) and (not v in vset) do inc(i);
    if i<=n then find:=i else find:=0;
  end;

procedure kruskal;
  var
    tot,i,j:integer;
  begin
    for i:=1 to n do vset:=;{初始化定义n个集合，第I个集合包含一个元素I}
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
sort;
{对所有边按权值递增排序，存于e中，e.v1与e.v2为边I所连接的两个顶点的序号，e.len为第I条边的长度}
    while p>0 do begin
      i:=find(e[q].v1);j:=find(e[q].v2);
      if i<>j then begin
        inc(tot,e[q].len);
        vset:=vset+vset[j];vset[j]:=[];
        dec(p);
      end;
      inc(q);
    end;
    writeln(tot);
  end;

2.最短路径
  A.标号法求解单源点最短路径：
    var
      a:array[1..maxn,1..maxn] of integer;
      b:array[1..maxn] of integer; {b指顶点i到源点的最短路径}
      mark:array[1..maxn] of boolean;

    procedure bhf;
      var
        best,best_j:integer;
      begin
        fillchar(mark,sizeof(mark),false);
     mark[1]:=true; b[1]:=0;{1为源点}
     repeat
       best:=0;
         for i:=1 to n do
          If mark then {对每一个已计算出最短路径的点}
           for j:=1 to n do
             if (not mark[j]) and (a[i,j]>0) then
            if (best=0) or (b+a[i,j]<best) then begin
              best:=b+a[i,j];  best_j:=j;
           end;
        if best>0 then begin
          b[best_j]:=best；mark[best_j]:=true;
        end;
      until best=0;
      end;{bhf}

   B.Floyed算法求解所有顶点对之间的最短路径：
      procedure floyed;
        begin
for I:=1 to n do
  for j:=1 to n do
  if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点}
   for k:=1 to n do {枚举中间结点}
     for i:=1 to n do
       for j:=1 to n do
         if a[i,k]+a[j,k]<a[i,j] then begin
        a[i,j]:=a[i,k]+a[k,j];
              p[I,j]:=p[k,j];
      end;
       end;

C. Dijkstra 算法：
var
      a:array[1..maxn,1..maxn] of integer;
      b,pre:array[1..maxn] of integer; {pre指最短路径上I的前驱结点}
      mark:array[1..maxn] of boolean;
procedure dijkstra(v0:integer);
  begin
    fillchar(mark,sizeof(mark),false);
    for i:=1 to n do begin
      d:=a[v0,i];
      if d<>0 then pre:=v0 else pre:=0;
    end;
    mark[v0]:=true;
    repeat   {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
      min:=maxint; u:=0; {u记录离1集合最近的结点}
      for i:=1 to n do
        if (not mark) and (d<min) then begin
          u:=i; min:=d;
      end;
      if u<>0 then begin
        mark[u]:=true;
        for i:=1 to n do
         if (not mark) and (a[u,i]+d[u]<d) then begin
           d:=a[u,i]+d[u];
           pre:=u;
        end;
      end;
    until u=0;
  end;

3.计算图的传递闭包
Procedure Longlink;
  Var
T:array[1..maxn,1..maxn] of boolean;
  Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
  For I:=1 to n do
    For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
  End;


4．无向图的连通分量
A.深度优先
  procedure dfs ( now,color: integer);
     begin
       for i:=1 to n do
        if a[now,i] and c=0 then begin {对结点I染色}
          c:=color;
          dfs(I,color);
        end;
end;

B 宽度优先（种子染色法）


5．关键路径
几个定义： 顶点1为源点，n为汇点。
a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 边活动最早开始时间 Ee, 若边I由<j,k>表示，则Ee = Ve[j];
d. 边活动最晚开始时间 El, 若边I由<j,k>表示，则El = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。
求解方法：
a. 从源点起topsort,判断是否有回路并计算Ve;
b. 从汇点起topsort,求Vl;
c. 算Ee 和 El;


6．拓扑排序
找入度为0的点，删去与其相连的所有边，不断重复这一过程。
例  寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.


7.回路问题
Euler回路(DFS)
定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点）

Hamilton回路
定义：经过图的每个顶点仅一次的回路。

一笔画
充要条件：图连通且奇点个数为0个或2个。

9．判断图中是否有负权回路 Bellman-ford 算法
  x,y,t分别表示第I条边的起点，终点和权。共n个结点和m条边。
   procedure bellman-ford
    begin
for I:=0 to n-1 do d:=+infinitive;
d[0]:=0;
for I:=1 to n-1 do
  for j:=1 to m do {枚举每一条边}
    if d[x[j]]+t[j]<d[y[j]] then d[y[j]]:=d[x[j]]+t[j];
for I:=1 to m do
  if d[x[j]]+t[j]<d[y[j]] then return false else return true;
    end;

10．第n最短路径问题
*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。
*同理，第n最短路径可在求解第n-1最短路径的基础上求解。