江苏网上训练解题报告roads

1、公路解题（Roads Scholar）一中给出一个高速公路系统，求出在此系统上每个路牌上的城市。详见 task.doc。本题的之处并不是算法，而是题意。由于原题是英文的，而全题的关键之处仅是题中一句十分难懂的英文长句，所以在推敲此句的意思上我花了很多功夫（英语也是相当重要的）。但实际上本题的就是一个最短路的Floyd 算法。题目要求路牌所在的公路是交叉路口到城市X 最短路的一部分，因此想到最短路是顺理成章的，而究竟是用 Dijstra 还是 Floyd 呢？注意到本题的最短路不是单源的，它可能有多个源和多个汇，所以无论从算法上还是编程复杂度上 Floyd 都是首选。先用 Floyd 求出任意两

2、个交叉路口 i、j 之间的最短距离 f(i,j)，然后对每个公路牌P，设它所在的路段是从路口 A 到路口 B，则若某城市 X 满足：dist(A,B)+f(B,X)=f(A,X)，（其中，dist(A,B)是公路 AB 的长度）那么城市X 将被记载在路牌 P 上。如此对每个路牌和每个城市求解一遍就得到了问题的解，算法十分简单。另外，以上算法依据的关键是题目中的“任两个路口之间的最短路有且只有 1 条”一句，所以若满足上述公式则城市 X 一定将被在 P 上。最后，在程序调试期间我发现了一个奇怪的现象：由于题目要求对数据四舍五入到整数，所以我使用了round(X)函数。几乎对所有的数据都只能对一半

3、的解，而且每次距离不是多 1 就是少 1。后来在测试round(X)函数时，我发现当X 是半整数时(如 0.5)，若它的整数部分是偶数则 round(X)将执行截尾功能，只有整数部分是奇数才执行舍入。不知这是否是 FP 的特性还是 Bug，所以我只好用了一个很小的误差数 zero=1e-5 来更正 round(X)函数，至于为何会有此现象，还盼望老师们明示。运行环境：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;最短路数组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;求任两个交叉路口之间的最短路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);交换城市号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