1、圖論程序整理Edmonds-Karpvar ans,i,j,k,s,t,tot,m,n,a,b,c:longint; u,v,w,next,other:array0.200 of longint; point,d,q,pre:array0.200 of longint;function min(a,b:longint):longint;begin if a>b then exit(b) else exit(a);end;procedure add_edge(a,b,c:longint);begin inc(k);uk:=a;vk:=b;wk:=c; nextk:=pointa;point

2、a:=k;otherk:=k+1; inc(k);uk:=b;vk:=a;wk:=0; nextk:=pointb;pointb:=k;otherk:=k-1;end;function found:boolean;var j,head,tail:longint;begin head:=0;tail:=1;q1:=s; fillchar(d,sizeof(d),127); ds:=0; while head<tail do begin inc(head); j:=pointqhead; while j<>0 do begin if (wj>0) and (duj+1<

3、;dvj) then begin dvj:=duj+1; prevj:=j; inc(tail);qtail:=vj; if vj=t then exit(true); end; j:=nextj;end; end; exit(false);end;procedure augment;var p,flow:longint;begin p:=t; flow:=maxlongint; while p<>s do begin flow:=min(flow,wprep); p:=uprep; end; ans:=ans+flow; p:=t; while p<>s do beg

4、in dec(wprep,flow); inc(wotherprep,flow); p:=uprep; end;end;begin readln(m,n); s:=1;t:=n;tot:=n; fillchar(point,sizeof(point),0); k:=0; for i:=1 to m do begin read(a,b,c); add_edge(a,b,c); end; ans:=0; while found do augment; writeln(ans);end.Dinicvar map:array0.201,0.201of longint; dis,q:array0.201

5、of longint; visit:array0.201of boolean; n,m,ans:longint; procedure init; var u,v,s,i:longint; begin readln(m,n); for i:=1 to m do begin readln(u,v,s); inc(mapu,v,s); end; end; function can_build:boolean; var sum,i,len,head,u,v:longint; begin can_build:=false; fillchar(visit,sizeof(visit),false); q0:

6、=n; visitn:=true; disn:=0; len:=0; head:=0; while head<=len do begin u:=qhead; for v:=1 to n do if (not visitv)and(mapvu>0) then begin inc(len); qlen:=v; visitv:=true; disv:=disu+1; if v=1 then can_build:=true; end; inc(head); end; end; function min(a,b:longint):longint; begin if a<b then e

7、xit(a) else exit(b); end; function bfs(u,flow:longint):longint; var v:longint; begin if u=n then exit(flow); for v:=1 to n do if (mapuv>0)and(disu=disv+1) then begin flow:=min(flow,mapuv); bfs:=bfs(v,flow); if bfs>0 then begin dec(mapuv,bfs); inc(mapvu,bfs); exit; end; end; exit(0); end; proce

8、dure dinic; var i,j,flow:longint; begin while can_build do begin while true do begin flow:=bfs(1,maxlongint); if flow=0 then break; ans:=ans+flow; end; end; end; procedure print; begin writeln(ans); end; begin init; dinic; print; end. kosaraju;const maxn=100;var /mapx,i 記錄與點x鄰接的第i個點的編號 mapx,0記錄和x鄰接的

9、點的個數(shù) map,map1:array1.maxn,0.maxnof integer; visit:array1.maxnof boolean; /記錄該點是否被遍歷過 list:array1.maxnof integer; /記錄n個點的遍歷次序 n,m,pos,scc:integer; /pos記錄進入list數(shù)組的點的個數(shù) scc記錄強連通分量的個數(shù) procedure init;var i,x,y:integer;begin readln(n,m); for i:=1 to m do begin readln(x,y); inc(mapx,0); mapx,mapx,0:=y; /存儲

10、原圖 inc(map1y,0); map1y,map1y,0:=x; /存儲反向的圖 end;end;procedure dfs(p:integer);var i,j,k:integer;begin visitp:=true; k:=mapp,0; for i:=1 to k do begin j:=mapp,i; if not visitj then dfs(j); end; inc(pos); listpos:=p;end;procedure dfs1(p:integer);var i,j,k:integer;begin visitp:=true; k:=map1p,0; for i:=1

11、 to k do begin j:=map1p,i; if not visitj then dfs1(j); end;end;procedure kosaraju;var i,j,k:integer;begin /dfs 正向深搜 fillchar(visit,sizeof(visit),false); for i:=1 to n do if not visiti then dfs(i); /dfs1 反向深搜 fillchar(visit,sizeof(visit),false); scc:=0; for i:=pos downto 1 do /每深搜完一次，表示找完一個強連通圖，增加scc

12、 if not visitlisti then begin dfs1(listi); inc(scc); end;end;begin init; pos:=0; kosaraju; writeln(scc);End.hungryvar a:array1.1000,1.1000 of boolean; b:array1.1000 of longint; c:array1.1000 of boolean; n,k,i,x,y,ans,m:longint;function path(x:longint):boolean;var i:longint;begin for i:=1 to n do if

13、axi and not ci then begin ci:=true; if (bi=0) or (path(bi) then begin bi:=x; exit(true); end; end; exit(false);end;procedure hungary;var i:longint;begin fillchar(b,sizeof(b),0); for i:=1 to m do begin fillchar(c,sizeof(c),0); if path(i) then inc(ans); end;end;begin fillchar(a,sizeof(a),0); readln(m,

14、n); for i:=1 to k do begin readln(x,y); axy:=true; end; ans:=0; hungary; writeln(ans);end. Edmonds-karp var t,g:array0.500,0.500of longint; tot,d,min,r:array0.500of longint; v:array0.500of boolean; q:array0.500of longint; head,tail,i,x,y,m,n,s,e,c,max,j:longint;procedure sssp;begin fillchar(v,sizeof

15、(v),false);v1:=true; fillchar(d,sizeof(d),0); fillchar(min,sizeof(min),127); q1:=1;tail:=1;head:=0; repeat inc(head); x:=qhead; for i:=1 to totx do begin y:=tx,i; if (gx,y>0)and(not vy) then begin inc(tail); qtail:=y; vy:=true; dy:=dx+1; ry:=x; if gx,y<minx then miny:=gx,y else miny:=minx; if

16、y=m then exit; end; end; until head>=tail;end;begin assign(input,'in.in'); reset(input); readln(n,m); for i:=1 to n do begin readln(s,e,c); inc(tots);ts,tots:=e; inc(tote);te,tote:=s; inc(gs,e,c); end; while true do begin sssp; if dm=0 then break else begin y:=m; for i:=1 to dm do begin x

17、:=ry; gx,y:=gx,y-minm; gy,x:=gy,x+minm; y:=x; end; inc(max,minm); end; end; writeln(max); close(input);end.Spfavar p,c,s,t:longint; a,b:array1.1000,1.1000 of longint; d:array1.1000,0.1000 of longint; v:array1.1000 of boolean; dist:array1.1000 of longint; head,tail:longint;procedure init;var i,x,y,z:

18、longint;begin read(p,c); for i:=1 to c do begin readln(x,y,z); inc(bx,0); bx,bx0:=y; axy:=z; inc(by0); by,by0:=x; ayx:=z; end; readln(s,t);end;procedure spfa(s:longint);var i,j,now,sum:longint;begin fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false); for j:=1 to p do distj:=maxlongint; diss:=0;vs:

19、=true;d1:=s; head:=1;tail:=1; while head<=tail do begin now:=dhead; for i:=1 to bnow0 do if distbnowi>distnow+anow,bnowi then begin distbnowi:=distnow+anow,bnowi;if not vbnowi then begin inctail); dtail:=bnowj; vbnowi:=true; end;end;vnow:=false; inc(head);end;end;procedure print;begin writeln(

20、distt);end;begin init; spfa(s); print;end. Primvar g:array1.100,1.100 of longint; min:array0.100 of longint; u:array0.100 of boolean; n,i,j,k,total:longint;begin readln(n); for i:=1 to n do begin for j:=1 to n do read(gij); end; fillchar(min,sizeof(min),$7f); min1:=0; fillchar(u,sizeof(u),1); for i:

21、=1 to n do begin k:=0; for j:=1 to n do if uj and (minj<mink) then k:=j;uk:=false;for j:=1 to n do if uj and (gkj<minj) then minj:=gkj; end; total:=0; for i:=1 to n do inc(total,mini); writeln(total);End. Ballman-Ford var f:array1.1000,1.2 of longint; ff,c:array1.1000 of real; a:array1.1000,1.

22、2 of longint; n,m,s,t,x,y,i,j:longint;begin assign(input,'in.in'); reset(input); readln(n); for i:=1 to n do readln(ai1,ai2); readln(m); fillchar(c,sizeof(c),$7f); fillchar(f,sizeof(f),$7f); for i:=1 to m do begin readln(x,y); fi1:=x; fi2:=y; ffi:=sqrt(sqr(ax1-ay1)+sqr(ax2-ay2); end; readln(

23、s,t); for i:=1 to m do begin if fi1=s then cfi2:=ffi; if fi2=s then cfi1:=ffi; end; for i:=1 to n do for j:=1 to m do begin if cfj1+ffj<cfj2 then cfj2:=cfj1+ffj; if cfj2+ffj<cfj1 then cfj1:=cfj2+ffj; end; writeln(ct:0:2); close(input);end.Dijistravar a:array1.100,1.2 of longint; c:array1.100 o

24、f real; b:array1.100 of boolean; f:array1.100,1.100 of real; n,i,j,k,x,y,m,s,e:longint; min:real;begin assign(input,'in.in'); reset(input); readln(n); for i:=1 to n do readln(ai1,ai2); readln(m); fillchar(f,sizeof(f),$5f); for i:=1 to m do begin readln(x,y); fxy:=sqrt(sqr(ax1-ay1)+sqr(ax2-ay

25、2); fyx:=fxy; end; readln(s,e); for i:=1 to n do ci:=fsi; for i:=1 to n-1 do begin min:=maxlongint; k:=0; for j:=1 to n do if (not bj) and (cj<min) then begin min:=cj; k:=j; end; if k=0 then break; bk:=true; for j:=1 to n do if ck+fkj<cj then cj:=ck+fkj; end; writeln(ce:0:2); close(input);end.

26、Floyedvar a:array1.100,1.2 of longint; f:array1.100,1.100 of real; n,i,j,k,x,y,m,s,e:longint;function max(a,b:real):real;begin if a>b then exit(b) else exit(a);end;begin readln(n); for i:=1 to n do readln(ai1,ai2); readln(m); for i:=1 to n do for j:=1 to n do fij:=maxlongint div 3; for i:=1 to m

27、do begin readln(x,y); fxy:=sqrt(sqr(ax1-ay1)+sqr(ax2-ay2); fyx:=fxy; end; readln(s,e); for k:=1 to n do for i:=1 to n do for j:=1 to n do fij:=max(fij,fik+fkj); writeln(fs,e:0:2);end.Tarjantarjan(u) DFNu=Lowu=+Index / 為節(jié)點u設(shè)定次序編號和Low初值 Stack.push(u) / 將節(jié)點u壓入棧中 for each (u, v) in E / 枚舉每一條邊 if (v is n

28、ot visted) / 如果節(jié)點v未被訪問過 tarjan(v) / 繼續(xù)向下找 Lowu = min(Lowu, Lowv) else if (v in S) / 如果節(jié)點v還在棧內(nèi) Lowu = min(Lowu, DFNv) if (DFNu = Lowu) / 如果節(jié)點u是強連通分量的根 repeat v = S.pop/將v退棧，為該強連通分量中一個頂點 print v until (u= v) Var a:array0.5000,0.5000 of boolean; stack,dfn,low,gpoint:array0.5000 of longint; v:array0.500

29、0 of boolean; top,root,ans,all,i,p,q,n,m:longint;function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b);end;procedure tarjan(p:longint);var i:longint;begin inc(all); lowp:=all; dfnp:=all; inc(top); stacktop:=p; vp:=true; for i:=1 to n do if ap,i then begin if dfni=0 then begin

30、tarjan(i); lowp:=min(lowp,lowi); end; if vi then lowp:=min(lowp,dfni); if (lowi>=dfnp) and (p<>1) then gpointp:=gpointp+1 else if p=1 then root:=root+1 else lowp:=min(lowp,dfni); /求割點 end; else if vi then lowp:=min(lowp,dfni); if lowp=dfnp then begin repeat vstacktop:=false; write(stacktop,

31、' '); dec(top); until stacktop+1=p; writeln; end; /求強連通分量end;procedure print;var i:longint;begin if root>1 then ans:=ans+1; for i:=2 to n do begin if gpointi>0 then begin ans:=ans+1; writeln(i); end; end; writeln(ans);end; / 求割點begin assign(input,'in.in'); assign(output,'ou

32、t.out'); reset(input); rewrite(output); readln(n,m); fillchar(a,sizeof(a),false); fillchar(v,sizeof(v),false); all:=0;top:=0; for i:=1 to m do begin readln(p,q); ap,q:=true; end; for i:=1 to n do if dfni=0 then tarjan(i); / print; close(input); close(output);end.拓撲排序O（V+E）數(shù)據(jù)結(jié)構(gòu)：indgri：頂點i的入度 stac

33、k:棧初始化 top：=0（棧頂指針置零）將初始化狀態(tài)所有入度為0的頂點壓棧I=0(計數(shù)器）while 棧非空（top>0) dobegin 棧頂?shù)捻旤cv出棧；top:=top-1; 輸出v；I：=I+1； for v 的每一個后繼頂點 u do dec（indgru);u的入度減一； if u 的入度變?yōu)? then 頂點u入棧end； kruskal;const MXN=1000; type rqmap=record s,t,v:longint; end; var map:array1.MXN*MXN of rqmap; father:array1.MXN of longint; n

34、,m,i,ingraph,ans:longint; procedure qsort(b,e:longint);/排序 var i,j,x:longint; t:rqmap; begin i:=b;j:=e;x:=map(i+j)>>1.v; while (i<=j) do begin while (mapi.v<x) do inc(i); while (mapj.v>x) do dec(j); if (i<=j) then begin t:=mapi; mapi:=mapj; mapj:=t; inc(i); dec(j); end; end; if i<e then qsort(i,e); if j>b then qsor