ACM算法2

一、数论算法1．求两数的最大公约数functiongcd(a,b:integer):integer;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;2．求两数的最小公倍数functionlcm(a,b:integer):integer;beginifabthenswap(a,b);lcm:=a;whilelcmmodb0doinc(lcm,a);end;3．素数的求法A.小范围内判断一个数是否为质数：functionprime(n:integer):Boolean;varI:integer;beginforI:=2totrunc(sqrt(n))doifnmodI=0thenbeginprime:=false;exit;end;prime:=true;end;B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：proceduregetprime;vari,j:longint;p:array[1..50000]ofboolean;beginfillchar(p,sizeof(p),true);p[1]:=false;i:=2;whilei50000dobeginifp[i]thenbeginj:=i*2;whilej50000dobeginp[j]:=false;inc(j,i);end;end;inc(i);end;l:=0;fori:=1to50000doifp[i]thenbegininc(l);pr[l]:=i;end;end;{getprime}functionprime(x:longint):integer;vari:integer;beginprime:=false;fori:=1toldoifpr[i]=xthenbreakelseifxmodpr[i]=0thenexit;prime:=true;end;{prime}二、图论算法1．最小生成树A.Prim算法：procedureprim(v0:integer);varlowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcost[i]:=cost[v0,i];closest[i]:=v0;end;fori:=1ton-1dobegin{寻找离生成树最近的未加入顶点k}min:=maxlongint;forj:=1tondoif(lowcost[j]min)and(lowcost[j]0)thenbeginmin:=lowcost[j];k:=j;end;lowcost[k]:=0;{将顶点k加入生成树}{生成树中增加一条新的边k到closest[k]}{修正各点的lowcost和closest值}forj:=1tondoifcost[k,j]lwocost[j]thenbeginlowcost[j]:=cost[k,j];closest[j]:=k;end;end;end;{prim}B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。functionfind(v:integer):integer;{返回顶点v所在的集合}vari:integer;begini:=1;while(i=n)and(notvinvset[i])doinc(i);ifi=nthenfind:=ielsefind:=0;end;procedurekruskal;vartot,i,j:integer;beginfori:=1tondovset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}p:=n-1;q:=1;tot:=0;{p为尚待加入的边数，q为边集指针}sort;{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}whilep0dobegini:=find(e[q].v1);j:=find(e[q].v2);ifijthenbegininc(tot,e[q].len);vset[i]:=vset[i]+vset[j];vset[j]:=[];dec(p);end;inc(q);end;writeln(tot);end;2.最短路径A.标号法求解单源点最短路径：vara:array[1..maxn,1..maxn]ofinteger;b:array[1..maxn]ofinteger;{b[i]指顶点i到源点的最短路径}mark:array[1..maxn]ofboolean;procedurebhf;varbest,best_j:integer;beginfillchar(mark,sizeof(mark),false);mark[1]:=true;b[1]:=0;{1为源点}repeatbest:=0;fori:=1tondoIfmark[i]then{对每一个已计算出最短路径的点}forj:=1tondoif(notmark[j])and(a[i,j]0)thenif(best=0)or(b[i]+a[i,j]best)thenbeginbest:=b[i]+a[i,j];best_j:=j;end;ifbest0thenbeginb[best_j]:=best；mark[best_j]:=true;end;untilbest=0;end;{bhf}B.Floyed算法求解所有顶点对之间的最短路径：procedurefloyed;beginforI:=1tondoforj:=1tondoifa[I,j]0thenp[I,j]:=Ielsep[I,j]:=0;{p[I,j]表示I到j的最短路径上j的前驱结点}fork:=1tondo{枚举中间结点}fori:=1tondoforj:=1tondoifa[i,k]+a[j,k]a[i,j]thenbegina[i,j]:=a[i,k]+a[k,j];p[I,j]:=p[k,j];end;end;C.Dijkstra算法：vara:array[1..maxn,1..maxn]ofinteger;b,pre:array[1..maxn]ofinteger;{pre[i]指最短路径上I的前驱结点}mark:array[1..maxn]ofboolean;proceduredijkstra(v0:integer);beginfillchar(mark,sizeof(mark),false);fori:=1tondobegind[i]:=a[v0,i];ifd[i]0thenpre[i]:=v0elsepre[i]:=0;end;mark[v0]:=true;repeat{每循环一次加入一个离1集合最近的结点并调整其他结点的参数}min:=maxint;u:=0;{u记录离1集合最近的结点}fori:=1tondoif(notmark[i])and(d[i]min)thenbeginu:=i;min:=d[i];end;ifu0thenbeginmark[u]:=true;fori:=1tondoif(notmark[i])and(a[u,i]+d[u]d[i])thenbegind[i]:=a[u,i]+d[u];pre[i]:=u;end;end;untilu=0;end;3.计算图的传递闭包ProcedureLonglink;VarT:array[1..maxn,1..maxn]ofboolean;BeginFillchar(t,sizeof(t),false);Fork:=1tondoForI:=1tondoForj:=1tondoT[I,j]:=t[I,j]or(t[I,k]andt[k,j]);End;4．无向图的连通分量A.深度优先proceduredfs(now,color:integer);beginfori:=1tondoifa[now,i]andc[i]=0thenbegin{对结点I染色}c[i]:=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],若边I由j,k表示，则Ee[I]=Ve[j];d.边活动最晚开始时间El[I],若边I由j,k表示，则El[I]=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[I],y[I],t[I]分别表示第I条边的起点，终点和权。共n个结点和m条边。procedurebellman-fordbeginforI:=0ton-1dod[I]:=+infinitive;d[0]:=0;forI:=1ton-1doforj:=1tomdo{枚举每一条边}ifd[x[j]]+t[j]d[y[j]]thend[y[j]]:=d[x[j]]+t[j];forI:=1tomdoifd[x[j]]+t[j]d[y[j]]thenreturnfalseelsereturntrue;end;10．第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。三、背包问题*部分背包问题可有贪心法求解：计算Pi/Wi数据结构：w[i]:第i个背包的重量；p[i]:第i个背包的价值；1．0-1背包：每个背包只能使用一次或有限次(可转化为一次)：A.求最多可放入的重量。NOIP2001装箱问题有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积(正整数)。要求从n个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。l搜索方法proceduresearch(k,v:integer);{搜索第k个物品，剩余空间为v}vari,j:integer;beginifvbestthenbest:=v;ifv-(s[n]-s[k-1])=bestthenexit;{s[n]为前n个物品的重量和}ifk=nthenbeginifvw[k]thensearch(k+1,v-w[k]);search(k+1,v);end;end;lDPF[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现:将最优化问题转化为判定性问题f[I,j]=f[i-1,j-w[i]](w[I]=j=v)边界：f[0,0]:=true.ForI:=1tondoForj:=w[I]tovdoF[I,j]:=f[I-1,j-w[I]];优化：当前状态只与前一阶段状态有关，可降至一维。F[0]:=true;ForI:=1tondobeginF1:=f;Forj:=w[I]tovdoIff[j-w[I]]thenf1[j]:=true;F:=f1;End;B.求可以放入的最