bellman算法判定是否存在负权回路程序清单

《bellman算法判定是否存在负权回路程序清单》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、NOIP2004复习资料1．Bellman－Ford（判断是否存在负权回路）思想：如果无向图边上存在负权回路，则回路边上的边（U，V）的d[v]值一定小于d[u]+w[u,v]。程序：说明：x为边的起始点，y为边的终点，t为边的权值。ProgramBellman_Ford;constfin=’bellman.in’;fout=’bellman,out’;maxn=100;varx,y,t,d:array[0..maxn]ofinteger;n,e:integer;procedureinit;varI,j:integer;beginfillchar(x,sizeof(x

2、),0);fillchar(y,sizeof(y),0);fillchar(t,sizeof(t),0);fillchar(d,sizeof(d),$6F);e:=0;assign(input,fin);reset(input);readln(n);whilenoteofdobeginread(I,j);inc(e);x[e]:=I;y[e]:=j;read(t[e]);end;close(input);end;functionmain:boolean;varI,j:integer;begind[1]:=0;fori:=1ton-1doforj:=1toedoif(d

3、[x[j]]+t[j]

4、n,x0,y0:longint;functiongcd(a,b:longint;varx,y:longint):longint;vart:integer;beginifb=0thenbegingcd:=a;x:=1;y:=-1;endelsebegingcd:=gcd(b,amodb,x,y);t:=x;x:=y;y:=t-(adivb)*y;end;end;beginreadln(m,n);write(gcd(m,n,x0,y0),’=’);writeln(x0,’*’,m,’+’,y0,’*’,n);end.2．求模线性方程（组）A．求模线性方程思想：若要解的模线

5、性方程为ax=b(modn)，则1．求出d＝gcd(a,n)和满足d=ax`+ny`的x`和y`。这表明x`是方程ax`＝b(modn)的一个解。2．分析：若d不能被b整除，则ax＝b(modn)没有解。否则，其中第一个解的值为x0=x`*(b/d)modn。其余d－1个解可以通过对模n加上（n/d）的倍数来得到，即xi=(x0+i*(n/d))modn。zqyPage186/14/2021/NOIP2004复习资料程序：vara,b,x,y,I,x0,xi,n,d:integer;functiongcd(a,b:integer;varx,y:integer):int

6、eger;vart:integer;beginifb=0thenbegingcd:=a;x:=1;y:=0;endelsebegingcd:=gcd(b,amodb,x,y);t:=x;x:=y;y:=t-(adivb)*y;end;end;beginreadln(a,b,n);d:=gcd(a,n,x,y);ifbmodd<>0thenwriteln(‘NoAnswer’)elsebeginx0:=x*(bdivd)modn;whilex0<0doinc(x0,n);writeln(‘Answer1:’,x0);fori:=1tod-1dobeginxi:=(x0+

7、i*(ndivd))modn;writeln(‘Answer‘,i+1,’:’,xi);end;end;end.A．求模线性方程组思想：a=a1(modn1)a=a2(modn2)……a=ak(modnk)条件中模都互质。设N＝N1*N2*…*Nk;m1=N/N1=N2*N3*…*Nk;m2=N/N2=N1*N3*N4*…*Nk;mi=N/Ni=N1*…*Ni-1*Ni+1*…*Nk;……mk=N/Nk=N1*…Nk-1由于mi与ni互为质数，因此我们可以通过解下列模线性方程：m1*m1^-1=1(modN1)zqyPage186/14/2021/N