pascal省選模板

1、算法線段樹1平衡二叉樹3匈牙利算法8km算法9sap算法10rmq問題的st算法12樹狀數(shù)組13最小費(fèi)用最大流15tarjan算法17根堆21并查集22prim算法23計(jì)算幾何26a*算法31矩陣乘法34快速冪38線段樹線段樹示范程序program intervaltree; const inf=input.txt; ouf=output.txt; maxn=10000; type treenode=record /a,b:區(qū)間左右邊界，left,right:左右兒子,cover:是否被覆蓋 a,b,left,right,cover:longint; end; var tree:array 1

2、.maxn of treenode; number,tot,c,d:longint; /tot:線段樹節(jié)點(diǎn)總數(shù)procedure maketree(a,b:longint); /建樹var now:longint; /now必須為局部變量!(dfs中枚舉變量一樣的道理)begin inc(tot); /節(jié)點(diǎn)總數(shù)+1 now:=tot; treenow.a:=a; treenow.b:=b; treenow.cover:=0; /把a(bǔ),b數(shù)據(jù)寫入到treetot; if a+1b then begin treenow.left:=tot+1; maketree(a,(a+b) div 2); /

3、建左子樹 treenow.right:=tot+1; /(若now為全局變量，建左子樹會(huì)修改now的值，導(dǎo)致此處建樹不正確) maketree(a+b) div 2,b); /建右子樹 end; end; procedure insert(num:longint); /插入線段c,d(c,d為全局變量)到線段樹第num個(gè)節(jié)點(diǎn)區(qū)間begin if (c=treenum.a) and (treenum.b=d) then /若當(dāng)前區(qū)間被c,d覆蓋，則cover+1 treenum.cover:=treenum.cover+1 else begin /否則將區(qū)間c,d插到左右子樹中 if c(tre

4、enum.a+treenum.b) div 2 then insert(treenum.right); end; end; procedure delete(num:longint);/在線段樹第num個(gè)節(jié)點(diǎn)區(qū)間中刪除線段c,dbegin if (c=treenum.a) and (treenum.b=d) then /若當(dāng)前區(qū)間被c,d覆蓋，則cover-1 dec(treenum.cover) else begin /否則將區(qū)間c,d在左右子樹中刪除 if c(treenum.a+treenum.b) div 2 then delete(treenum.right); end; end;

5、procedure count(num:longint); /計(jì)算整個(gè)線段樹的測(cè)度(被覆蓋區(qū)間的總長度)begin if treenum.cover0 then /若當(dāng)前區(qū)間被完全覆蓋，則累加到number全局變量中 number:=number+(treenum.b-treenum.a) else begin /否則，若為部分覆蓋，則累加左右子樹的測(cè)度 if treenum.left0 then count(treenum.left); if treenum.right0 then count(treenum.right); end; end; begin assign(input,inf)

6、;reset(input); assign(output,ouf);rewrite(output); readln(c,d); /讀入總區(qū)間大小 maketree(c,d); /建樹 while not eof do begin readln(c,d); /向線段樹中插入線段c,d insert(1); end; count(1); /計(jì)算線段樹的測(cè)度 writeln(number); close(output); close(input); end.平衡二叉樹treap示范代碼：標(biāo)準(zhǔn)的代碼縮進(jìn)風(fēng)格，優(yōu)美的算法實(shí)現(xiàn)。經(jīng)典標(biāo)程，完全掌握后水平會(huì)提高很多不改變bst的性質(zhì)(在bst所有子樹中均滿足

7、：左子樹的所有節(jié)點(diǎn)=根=右子樹的所有節(jié)點(diǎn))通過旋轉(zhuǎn)操作，使根的hr最小(即所有的hr構(gòu)成堆的關(guān)系)$inline onvar /li,ri,vi:i號(hào)結(jié)點(diǎn)的左兒子、右兒子，關(guān)鍵值 /hri:i號(hào)節(jié)點(diǎn)的優(yōu)先值(treap所有子樹中,根的hr必須是最小的) /si:i號(hào)節(jié)點(diǎn)為根的子樹節(jié)點(diǎn)總數(shù) l,r,hr,s,v:array0.2000000of longint; n,root,m:longint; procedure init;/初始化begin readln(n); m:=0; /randomize; /考試要求程序每次運(yùn)行結(jié)果必須一致,慎用。確實(shí)要用：randomize 100; fillc

8、har(s,sizeof(s),0); fillchar(l,sizeof(l),0); fillchar(r,sizeof(r),0); root:=0;end;/旋轉(zhuǎn)是平衡二叉樹的精髓，它不會(huì)改變bst的性質(zhì)(左子樹=根=右子樹)/左旋使樹的左子樹深度+1,右子樹深度-1/右旋使樹的右子樹深度+1,左子樹深度-1procedure l_rotate(var x:longint);inline;/左旋以x為根的子樹（注意var參數(shù)及意義）var y:longint;begin y:=rx; /保存x的右兒子到y(tǒng)中 rx:=ly; /將y的左兒子作為x的右兒子 ly:=x; /x作為y的左兒子

9、 sy:=sx; /維護(hù)旋轉(zhuǎn)后的子樹大小 sx:=slx+srx+1; x:=y; /y為根end;procedure r_rotate(var x:longint);inline;/右旋以x為根的子樹var y:longint;begin y:=lx; lx:=ry; ry:=x; sy:=sx; sx:=slx+srx+1; x:=y;end;/插入（遞歸，if key=root,則插入到左子樹，否則到右子樹，直到盡頭再新建節(jié)點(diǎn)）procedure insert(var k,key:longint);inline;begin if k=0 then/已到盡頭，新建節(jié)點(diǎn)并寫入key及隨機(jī)值h

10、r begin inc(m); vm:=key; sm:=1; hrm:=random(maxlongint); k:=m;/修改k,使父節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)(修改前從父節(jié)點(diǎn)指向0) exit; end; inc(sk); if key=vk then/若keyhrk then /旋轉(zhuǎn) r_rotate(k); exit; end; if keyvk then begin insert(rk,key); if hrrkhrk then l_rotate(k); exit; end;end;(刪除:在k號(hào)節(jié)點(diǎn)為根的子樹中刪除key基本方法：由于是靜態(tài)結(jié)構(gòu)，為了提高效率，并沒真正刪除若找到則刪除，若沒

11、找到，則刪除查找盡頭的節(jié)點(diǎn)主程序中需判斷返回值，若不等于key,重新插入key即可找到后的處理： 若為葉節(jié)點(diǎn)，直接刪除，否則，將要?jiǎng)h除的節(jié)點(diǎn)左子樹的最右節(jié)點(diǎn)（思考：為什么？）代替它)function delete(var k:longint;key:longint):longint;inline;begin dec(sk);/維護(hù)節(jié)點(diǎn)總數(shù) /如果找到，或已到盡頭 if (key=vk)or(lk=0)and(keyvk) then begin delete:=vk;/返回要?jiǎng)h除的節(jié)點(diǎn)（不一定=key） if (lk=0)or(rk=0) then /若左右子樹只有一個(gè)，則讓兒子代替根即可 be

12、gin k:=lk+rk;/用兒子替換當(dāng)前要?jiǎng)h除的節(jié)點(diǎn) exit; end; vk:=delete(lk,key+1);/k左右子樹都有，則用左子樹的最右節(jié)點(diǎn)替換k exit; end; if key=vk then/若kvk then exit(delete(rk,key);end;function find(var k,key:longint):boolean;inline;/查找begin if k=0 then/遞歸邊界 exit(false); if keyvk then find:=find(rk,key) else find:=(vk=key)or find(lk,key);en

13、d;/key的排名(key排在第幾，按從小到大的順序)function rank(var t,key:longint):longint;inline;begin if t=0 then exit(1); if key=vt then rank:=rank(lt,key) else rank:=slt+1+rank(rt,key);end;function select(var t:longint;k:longint):longint;inline;/選擇排在第k位的數(shù)begin if k=slt+1 then/若找到第k位的節(jié)點(diǎn)，則返回節(jié)點(diǎn)key值 exit(vt); if k=slt the

14、n/遞歸 select:=select(lt,k) else select:=select(rt,k-1-slt);end;function pred(var t,key:longint):longint;inline;/找key的前趨begin if t=0 then exit(key); if key=vt then/key根，原問題等價(jià)于在右子樹中找key，但右兒子返回時(shí)，要判斷你是不是key的前趨 pred:=pred(rt,key);/右子樹的返回值 if pred=key then /如果右子樹的返回值=key說明在右子樹中沒找到key的前趨 pred:=vt; /右子樹沒有key

15、的前趨，那你就是了。 end;end;function succ(var t,key:longint):longint;inline;/找key的后繼begin if t=0 then exit(key); if vtlxi then lxi:=wi,j; end; for k:=1 to n do repeat fillchar(vx,sizeof(vx),0); fillchar(vy,sizeof(vy),0); if find(k) then break; d:=255; for i:=1 to n do if vxi then for j:=1 to n do if not vyj

16、then if lxi+lyj-wi,jd then d:=lxi+lyj-wi,j; for i:=1 to n do begin if vxi then dec(lxi,d); if vyi then inc(lyi,d); end; until false; ans:=0; for i:=1 to n do inc(ans,wmi,i); writeln(ans); until seekeof;end.sap算法var g:array0.1001,0.1001 of longint; d,dv:array0.1001 of longint; flow,ans,m,n:longint;pr

17、ocedure init;begin assign(input,ditch.in); assign(output,ditch.out); reset(input); rewrite(output);end;procedure terminate;begin close(input); close(output); halt;end;function min(a,b:longint):longint;begin if a0) and (dx=di+1) then begin k:=dfs(i,min(flow-dfs,gx,i); dec(gx,i,k); inc(gi,x,k); inc(df

18、s,k); if dfs=flow then exit; end; if d1=n then exit; dec(dvdx); if dvdx=0 then d1:=n; inc(dx); inc(dvdx);end;procedure main;begin ans:=0; dv1:=n; while d1n do begin flow:=dfs(1,maxlongint); inc(ans,flow); end; writeln(ans);end;begin init; readdata; main; terminate;end.rmq問題的st算法var f:array0.100001,0

19、.30 of longint; n,m:longint;function min(a,b:longint):longint;begin if a0 dobegin inc(ca); a:=a-lowbit(a);end;end;function sum(x:longint):longint;vara,total:longint;begintotal:=0;a:=x;while a=n dobegin total:=total+ca; a:=a+lowbit(a);end;sum:=total;end;procedure readdata;varb,i,l,r,t:longint;beginre

20、adln(n,m);for i:=1 to m dobegin read(t); if t=1 then begin readln(l,r); chaozuo(r); chaozuo(l-1); end else begin readln(l); b:=sum(l) mod 2; writeln(b); end;end;end;begininit;readdata;terminate;end.最小費(fèi)用最大流var g,cost:array0.1000000,0.1000000 of longint; best,last:array0.1000000 of longint; m,n:longin

21、t; procedure readdata;var i,x,y,w,t:longint;begin fillchar(cost,sizeof(cost),$0f); readln(n,m); for i:=1 to m do begin readln(x,y,t,w); costx,y:=w; costy,x:=w; gx,y:=t; end;end;procedure main;var i,j,d,ans:longint; change:boolean;begin ans:=0; repeat fillchar(last,sizeof(last),0); fillchar(best,size

22、of(best),$0f); last1:=maxlongint; best1:=0; repeat change:=false; for i:=1 to n do if besti0) and (besti+costi,j1000000 then break; i:=n; d:=maxlongint; repeat if glasti,id then d:=glasti,i; i:=lasti; until i=1; inc(ans,d*bestn); i:=n; repeat dec(glasti,i,d); inc(gi,lasti,d); i:=lasti; until i=1; un

23、til false; writeln(ans);end;begin readdata; main; readln; readln;end.tarjan算法$m 10000000type node=point; point=record data:longint; next:node; end;var a,b:array0.500001 of node; instack,bar,bar2:array0.500001 of boolean; s,n,m,k,stacki,now,colori:longint; dd,color,back,stack,time,best,money,money2:a

24、rray0.500001 of longint;procedure init;begin assign(input,atm.in); assign(output,atm.out); reset(input); rewrite(output);end;procedure terminate;begin close(input); close(output); halt;end;procedure insert(x,y:longint); inline;var p:node;begin new(p); p.data:=y; p.next:=ax; ax:=p;end;procedure readd

25、ata;var i,x,y:longint;begin readln(n,m); for i:=1 to m do begin readln(x,y); insert(x,y); end; for i:=1 to n do readln(moneyi); readln(s,k); for i:=1 to k do begin read(x); barx:=true; end;end;function min(a,b:longint):longint; inline;begin if ab then exit(a) else exit(b);end;procedure tarjan(x:long

26、int); inline;var p:node;begin inc(now); timex:=now; backx:=now; inc(stacki); stackstacki:=x; instackx:=true; p:=ax; while pnil do begin if timep.data=0 then begin tarjan(p.data); backx:=min(backx,backp.data); end else if instackp.data then begin backx:=min(backx,backp.data); end; p:=p.next; end; if

27、timex=backx then begin inc(colori); while (stackstackix) and (stacki0) do begin colorstackstacki:=colori; instackstackstacki:=false; dec(stacki); end; colorstackstacki:=colori; instackstackstacki:=false; dec(stacki); end;end;procedure spfa(x:longint); inline;var p:node; h,t:longint;begin dd1:=x; ins

28、tackx:=true; bestx:=money2x; h:=0; t:=1; while ht do begin h:=(h+1) mod 100000; p:=bddh; instackddh:=false; while pnil do begin if bestp.databestddh+money2p.data then begin bestp.data:=bestddh+money2p.data; if not instackp.data then begin t:=(t+1) mod 100000; ddt:=p.data; instackddt:=true; end; end;

29、 p:=p.next; end; end;end;procedure main;var i,ans:longint; p,p2:node;begin now:=0; stacki:=0; colori:=0; for i:=1 to n do if timei=0 then tarjan(i); for i:=1 to n do begin inc(money2colori,moneyi); if bari then bar2colori:=true; p:=ai; while pnil do begin if coloricolorp.data then begin new(p2); p2.

30、data:=colorp.data; p2.next:=bcolori; bcolori:=p2; end; p:=p.next; end; end; fillchar(instack,sizeof(instack),0); fillchar(best,sizeof(best),0); spfa(colors); ans:=0; for i:=1 to colori do if (bestians) and bar2i and (besti100000000) then ans:=besti; writeln(ans);end;begin init; readdata; main; termi

31、nate;end.根堆最大堆和最小堆是二叉堆的兩種形式。 最大堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最大者。 最小堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最小者。 而最大-最小堆集結(jié)了最大堆和最小堆的優(yōu)點(diǎn)，這也是其名字的由來。 最大-最小堆是最大層和最小層交替出現(xiàn)的二叉樹，即最大層結(jié)點(diǎn)的兒子屬于最小層，最小層結(jié)點(diǎn)的兒子屬于最大層。 以最大（?。咏Y(jié)點(diǎn)為根結(jié)點(diǎn)的子樹保有最大（小）堆性質(zhì)：根結(jié)點(diǎn)的鍵值為該子樹結(jié)點(diǎn)鍵值中最大（?。╉?xiàng)。 最小堆的實(shí)現(xiàn)var a:array1.10000 of longint; i,n,tot,tt,len:longint;procedure down(x,n:longint);

32、var k,r,b:longint;begin b:=ax; r:=x; k:=r*2; while k=n do begin if (kak+1) then inc(k); if b1 do begin k:=r shr 1; if bak then break; ar:=ak; r:=k; end; ar:=b;end;begin read(n); for i:=1 to n do read(ai); for i:=n div 2 downto 1 do down(i,n); tot:=0; len:=n; for i:=1 to n-1 do begin tt:=a1; a1:=alen

33、; dec(len); down(1,len); inc(a1,tt); inc(tot,a1); down(1,len); end; writeln(tot);end.并查集var father:array1.5000of integer; i,j,k,p,n,m:integer; function getfather(v:integer):integer; begin if fatherv=v then exit(v); fatherv:=getfather(fatherv); getfather:=fatherv; end; procedure merge(x,y:integer); b

34、egin x:=getfather(x); y:=getfather(y); fatherx:=y; end; function judge(x,y:integer):boolean; begin x:=getfather(x); y:=getfather(y); if x=y then exit(true) else exit(false); end; begin readln(n,m,p); for i:=1 to n do fatheri:=i;預(yù)處理 for i:=1 to m do begin read(j,k); merge(j,k); end; for i:=1 to p do begin read(j,k); if judge(j,k) then writeln(yes) else writeln(no); end; end.prim算法1.1 實(shí)際背景與算法實(shí)際背景:要在n個(gè)居民點(diǎn)之間架設(shè)煤氣管道,很顯然最多可架設(shè) n(n-1)/2條管道,然而要連通n個(gè)居民點(diǎn)架設(shè)n-1條管道(無環(huán)出現(xiàn))就可以了,為了使造價(jià)最小,選擇哪n-1條邊?這就是最小生成樹問題。算法1（prim算法）：1）圖采用