江蘇網(wǎng)上訓(xùn)練解題報(bào)告roads

1、公路解題（Roads Scholar）一中給出一個(gè)高速公路系統(tǒng)，求出在此系統(tǒng)上每個(gè)路牌上的城市。詳見 task.doc。本題的之處并不是算法，而是題意。由于原題是英文的，而全題的關(guān)鍵之處僅是題中一句十分難懂的英文長句，所以在推敲此句的意思上我花了很多功夫（英語也是相當(dāng)重要的）。但實(shí)際上本題的就是一個(gè)最短路的Floyd 算法。題目要求路牌所在的公路是交叉路口到城市X 最短路的一部分，因此想到最短路是順理成章的，而究竟是用 Dijstra 還是 Floyd 呢？注意到本題的最短路不是單源的，它可能有多個(gè)源和多個(gè)匯，所以無論從算法上還是編程復(fù)雜度上 Floyd 都是首選。先用 Floyd 求出任意兩

2、個(gè)交叉路口 i、j 之間的最短距離 f(i,j)，然后對(duì)每個(gè)公路牌P，設(shè)它所在的路段是從路口 A 到路口 B，則若某城市 X 滿足：dist(A,B)+f(B,X)=f(A,X)，（其中，dist(A,B)是公路 AB 的長度）那么城市X 將被記載在路牌 P 上。如此對(duì)每個(gè)路牌和每個(gè)城市求解一遍就得到了問題的解，算法十分簡單。另外，以上算法依據(jù)的關(guān)鍵是題目中的“任兩個(gè)路口之間的最短路有且只有 1 條”一句，所以若滿足上述公式則城市 X 一定將被在 P 上。最后，在程序調(diào)試期間我發(fā)現(xiàn)了一個(gè)奇怪的現(xiàn)象：由于題目要求對(duì)數(shù)據(jù)四舍五入到整數(shù)，所以我使用了round(X)函數(shù)。幾乎對(duì)所有的數(shù)據(jù)都只能對(duì)一半

3、的解，而且每次距離不是多 1 就是少 1。后來在測試round(X)函數(shù)時(shí)，我發(fā)現(xiàn)當(dāng)X 是半整數(shù)時(shí)(如 0.5)，若它的整數(shù)部分是偶數(shù)則 round(X)將執(zhí)行截尾功能，只有整數(shù)部分是奇數(shù)才執(zhí)行舍入。不知這是否是 FP 的特性還是 Bug，所以我只好用了一個(gè)很小的誤差數(shù) zero=1e-5 來更正 round(X)函數(shù)，至于為何會(huì)有此現(xiàn)象，還盼望老師們明示。運(yùn)行環(huán)境：Free PascalP133MHz16M progrroblem_F_Roads; ACM2001 East Central Regional Contesetconst inf=roads.in; ouf=roads.out;

4、zero=1e-5; maxn=30;var f,dist:array0.maxn,0.maxn of real;最短路數(shù)組name:array0.maxn of string; mark:array0.maxn of fin,fou:text;n,m,k,s:eger;城市名;procedure init;初始化var i,j,i1,i2: d:real; ch:char;eger;程序及注釋算法分析問題描述beginassign(fin,inf); reset(fin); assign(fou,ouf); rewrite(fou); readln(fin,n,m,k);for i:=0 t

5、o n-1 dofor j:=0 to n-1 do disti,j:=1e30; for i:=1 to m dobegin readln(fin,i1,i2,d); disti1,i2:=d;disti2,i1:=d; end;fillchar(mark,sizeof(mark),false); for j:=1 to k dobegin readln(fin,i,ch,namei); marki:=true;end; end;procedure floyd;求任兩個(gè)交叉路口之間的最短路var k,i,j: begineger;for i:=0 to n-1 do for j:=0 to

6、n-1 do beginif i=j then begin fi,j:=0; continue end; fi,j:=disti,j;end;for k:=0 to n-1 do for i:=0 to n-1 dofor j:=0 to n-1 doif (fi,k1e30)and(fk,j1e30) then if fi,k+fk,j+zerofi,j thenfi,j:=fi,k+fk,jend;procedure solve; var tot,i1,i2,j1,i,j:主求解過程 eger;city:array1.30,1.2 of d:real;eger;procedure chan

7、ge(i1,j1:eger);交換城市號(hào)var t: begineger;t:=cityi1,2; cityi1,2:=cityj1,2;cityj1,2:=t; t:=cityi1,1;cityi1,1:=cityj1,1; cityj1,1:=tend;begin readln(fin,s); for i:=1 to s do beginreadln(fin,i1,i2,d); tot:=0; fillchar(city,sizeof(city),0); for j:=0 to n-1 doif markj thenif abs(disti1,i2+fi2,j-fi1,j)cityj1,2 then change(i1,j1) elseif cityi1,2=cityj1,2 thenif namecityi1,1namecityj1,1 then change(i1,j1);for i1:=1 to tot do begin輸出write(fou,namecityi1,1);for j1:=1 to 20-length(namecityi1,1) do write(fou, ); if (i=s)and(i1=tot) then write(f