主机屋怎么做网站/百度网页版 入口

问题

给定你一个有向图，让你求两点之间所有可行路径上的最大值之中的最小值。多组数据

分析

经典的floyd算法的变形，a[i,j]表示i，j两点之间所有可行路径上的最大值之中的最小值，我们可以的到这样的方程

a[i,j]:=min{a[i,j],max{a[i,k],a[k,j]}};很好理解。

code

program liukee;
vara:array[0..201,0..201] of double;n,tt:longint;procedure init;
varx,y:array[0..202] of double;i,j:longint;
beginfillchar(x,sizeof(x),0);fillchar(y,sizeof(y),0);for i:=1 to n doreadln(x[i],y[i]);for i:=1 to n dofor j:=1 to n doif i<>j thena[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));for i:=1 to n dofor j:=1 to n doif a[i,j]=0 then a[i,j]:=maxlongint>>1;
end;function max(a,b:double):double;
beginif a>b then exit(a) else exit(b);
end;procedure doit;
vari,j,k:longint;
beginfor k:=1 to n dofor i:=1 to n dofor j:=1 to n doif i<>j thenif (k<>i)and(k<>j) thenif a[i,j]>max(a[i,k],a[k,j]) then a[i,j]:=max(a[i,k],a[k,j]);writeln('Frog Distance = ',a[1,2]:0:3);writeln;
end;beginreadln(n);tt:=0;while n<>0 dobegininc(tt);fillchar(a,sizeof(a),0);init;writeln('Scenario #',tt);doit;readln;readln(n);end;
end.

反思

一定要先循环k！！！！！

要联想到合适的经典算法，floyd求最值，用到的是一种动态规划的思想。