【题目描述】
有n个小区，并且任意小区之间都有两条单向道路（a到b，b到a）相连。因为最近下了很多暴雨，很多道路都被淹了，不同的道路泥泞程度不同。经过对近期天气和地形的科学分析，绘出了每条道路能顺利通过的时间以及这条路的长度。
现在某人在小区1，他希望能够很顺利地到达目的地小区n，请帮助他找出一条从小区1出发到达小区n的所有路线中（总路程/总时间）最大的路线，并告诉他这个值。
【输入描述】
第一行包含一个整数n，为小区数。
接下来n*n的矩阵P，其中第i行第j个数表示从小区i到小区j的道路长度为P[i,j]。第i行第i个数的元素为0，其余保证为正整数。
接下来n*n的矩阵T，其中第i行第j个数表示从小区i到小区j需要的时间为T[i,j]。第i行第i个数的元素为0，其余保证为正整数。
【输出描述】
写入一个实数S，为小区1到达n的最大答案，S精确到小数点后3位。
【样例输入】
3
0 8 7
9 0 10
5 7 0
0 7 6
6 0 6
6 2 0
【样例输出】
2.125
【数据范围及提示】
【数据说明】
30%的数据，n <= 20；
100%的数据，n <= 100，p,t <= 10000。
源代码： #include<cstdio> #include<cstring> #include<queue> using namespace std; queue <int> h; int n,vis[101],p[101][101],t[101][101]; double left=0.0,right=10000.0,num=0.0001,ans=0,i[101][101],dis[101]; bool f[101]; bool SPFA(double mid) //SPFA求最长路径。 { for (int a=1;a<=n;a++) for (int b=1;b<=n;b++) i[a][b]=(double)p[a][b]-(double)t[a][b]*mid; //在本题中，应特别注意double类型的更改和转换。 memset(dis,-0x3f,sizeof(dis)); //赋极小值。 memset(f,0,sizeof(f)); memset(vis,0,sizeof(vis)); //判断是否为环。 while (h.size()) h.pop(); h.push(1); f[1]=true; dis[1]=0; vis[1]=1; while (h.size()) { int k=h.front(); for (int a=1;a<=n;a++) if (i[k][a]+dis[k]>dis[a]) { dis[a]=i[k][a]+dis[k]; if (!f[a]) { h.push(a); f[a]=true; vis[a]++; // if (vis[a]>n) return 1; } } f[k]=false; h.pop(); } return dis[n]>=0?1:0; //判断是否具有更优解。 } int main() { scanf("%d",&n); for (int a=1;a<=n;a++) for (int b=1;b<=n;b++) scanf("%d",&p[a][b]); for (int a=1;a<=n;a++) for (int b=1;b<=n;b++) scanf("%d",&t[a][b]); while (right-left>num) { double mid=(left+right)/2.0; if (SPFA(mid)) left=ans=mid; else right=mid; } printf("%.3lf",ans); return 0; } /* 一道有趣的变式题： (总路程/总时间)max=((s1+s2+...sN)/(t1+t2+...+tN))max=ans 经变换可以得到： (s1+s2+...+sN)=(t1+t2+...+tN)*ans 即：(s1-t1*ans)+(s2-t2*ans)+...+(sN-tN*ans)=0 把上述内容以图论形式转换，可以得到此问题的解法：二分答案+SPFA。 注意： N个点，则第K点最多入度为(N-1)，当入队次数超过N时，则必然有某条边重复了，存在环。 */