一数论算法
求两数的最大公约数
function gcd(ab:integer):integer;
begin
if b= then gcd:=a
else gcd:=gcd (ba mod b);
end ;
求两数的最小公倍数
function lcm(ab:integer):integer;
begin
if a
lcm:=a;
while lcm mod b> do inc(lcma);
end;
素数的求法
A小范围内判断一个数是否为质数
function prime (n: integer): Boolean;
var I: integer;
begin
for I:= to trunc(sqrt(n)) do
if n mod I= then begin
prime:=false; exit;
end;
prime:=true;
end;
B判断longint范围内的数是否为素数(包含求以内的素数表)
procedure getprime;
var
ij:longint;
p:array[] of boolean;
begin
fillchar(psizeof(p)true);
p[]:=false;
i:=;
while i< do begin
if p[i] then begin
j:=i*;
while j< do begin
p[j]:=false;
inc(ji);
end;
end;
inc(i);
end;
l:=;
for i:= to do
if p[i] then begin
inc(l);pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:= to l do
if pr[i]>=x then break
else if x mod pr[i]= then exit;
prime:=true;
end;{prime}
二图论算法
最小生成树
APrim算法
procedure prim(v:integer);
var
lowcostclosest:array[maxn] of integer;
ijkmin:integer;
begin
for i:= to n do begin
lowcost[i]:=cost[vi];
closest[i]:=v;
end;
for i:= to n do begin
{寻找离生成树最近的未加入顶点k}
min:=maxlongint;
for j:= to n do
if (lowcost[j]) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:= to n do
if cost[kj]
lowcost[j]:=cost[kj];
closest[j]:=k;
end;
end;
end;{prim}
BKruskal算法(贪心)
按权值递增顺序删去图中的边若不形成回路则将此边加入最小生成树
function find(v:integer):integer; {返回顶点v所在的集合}
var i:integer;
begin
i:=;
while (i<=n) and (not v in vset[i]) do inc(i);
if i<=n then find:=i else find:=;
end;
procedure kruskal;
var
totij:integer;
begin
for i:= to n do vset[i]:=[i];{初始化定义n个集合第I个集合包含一个元素I}
p:=n; q:=; tot:=; {p为尚待加入的边数q为边集指针}
sort;
{对所有边按权值递增排序存于e[I]中e[I]v与e[I]v为边I所连接的两个顶点的序号e[I]len为第I条边的长度}
while p> do begin
i:=find(e[q]v);j:=find(e[q]v);
if i<>j then begin
inc(tote[q]len);
vset[i]:=vset[i]+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
最短路径
A标号法求解单源点最短路径
var
a:array[maxnmaxn] of integer;
b:array[maxn] of integer; {b[i]指顶点i到源点的最短路径}
mark:array[maxn] of boolean;
procedure bhf;
var
bestbest_j:integer;
begin
fillchar(marksizeof(mark)false);
mark[]:=true; b[]:=;{为源点}
repeat
best:=;
for i:= to n do
If mark[i] then {对每一个已计算出最短路径的点}
for j:= to n do
if (not mark[j]) and (a[ij]>) then
if (best=) or (b[i]+a[ij]
best:=b[i]+a[ij]; best_j:=j;
end;
if best> then begin
b[best_j]:=best;mark[best_j]:=true;
end;
until best=;
end;{bhf}
BFloyed算法求解所有顶点对之间的最短路径
procedure floyed;
begin
for I:= to n do
for j:= to n do
if a[Ij]> then p[Ij]:=I else p[Ij]:=; {p[Ij]表示I到j的最短路径上j的前驱结点}
for k:= to n do {枚举中间结点}
for i:= to n do
for j:= to n do
if a[ik]+a[jk]
a[ij]:=a[ik]+a[kj];
p[Ij]:=p[kj];
end;
end;
C Dijkstra 算法
var
a:array[maxnmaxn] of integer;
bpre:array[maxn] of integer; {pre[i]指最短路径上I的前驱结点}
mark:array[maxn] of boolean;
procedure dijkstra(v:integer);
begin
fillchar(marksizeof(mark)false);
for i:= to n do begin
d[i]:=a[vi];
if d[i]<> then pre[i]:=v else pre[i]:=;
end;
mark[v]:=true;
repeat {每循环一次加入一个离集合最近的结点并调整其他结点的参数}
min:=maxint; u:=; {u记录离集合最近的结点}
for i:= to n do
if (not mark[i]) and (d[i]
u:=i; min:=d[i];
end;
if u<> then begin
mark:=true;
for i:= to n do
if (not mark[i]) and (a[ui]+d
d[i]:=a[ui]+d;
pre[i]:=u;
end;
end;
until u=;
end;
计算图的传递闭包
Procedure Longlink;
Var
T:array[maxnmaxn] of boolean;
Begin
Fillchar(tsizeof(t)false);
For k:= to n do
For I:= to n do
For j:= to n do T[Ij]:=t[Ij] or (t[Ik] and t[kj]);
End;
无向图的连通分量
A深度优先
procedure dfs ( nowcolor: integer);
begin
for i:= to n do
if a[nowi] and c[i]= then begin {对结点I染色}
c[i]:=color;
dfs(Icolor);
end;
end;
B 宽度优先(种子染色法)
关键路径
几个定义 顶点为源点n为汇点
a 顶点事件最早发生时间Ve[j] Ve [j] = max{ Ve [j] + w[Ij] }其中Ve () = ;
b 顶点事件最晚发生时间 Vl[j] Vl [j] = min{ Vl[j] – w[Ij] }其中 Vl(n) = Ve(n);
c 边活动最早开始时间 Ee[I] 若边I由表示则Ee[I] = Ve[j];
d 边活动最晚开始时间 El[I] 若边I由表示则El[I] = Vl[k] – w[jk];
若 Ee[j] = El[j] 则活动j为关键活动由关键活动组成的路径为关键路径
求解方法
a 从源点起topsort判断是否有回路并计算Ve;
b 从汇点起topsort求Vl;
c 算Ee 和 El;
拓扑排序
找入度为的点删去与其相连的所有边不断重复这一过程
例 寻找一数列其中任意连续p项之和为正任意q 项之和为负若不存在则输出NO
回路问题
Euler回路(DFS)
定义经过图的每条边仅一次的回路(充要条件图连同且无奇点)
Hamilton回路
定义经过图的每个顶点仅一次的回路
一笔画
充要条件图连通且奇点个数为个或个
判断图中是否有负权回路 Bellmanford 算法
x[I]y[I]t[I]分别表示第I条边的起点终点和权共n个结点和m条边
procedure bellmanford
begin
