时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond

题目描述 Description

CS有n个小区，并且任意小区之间都有两条单向道路（a到b，b到a）相连。因为最近下了很多暴雨，很多道路都被淹了，不同的道路泥泞程度不同。小A经过对近期天气和地形的科学分析，绘出了每条道路能顺利通过的时间以及这条路的长度。

现在小A在小区1，他希望能够很顺利地到达目的地小区n，请帮助小明找出一条从小区1出发到达小区n的所有路线中（总路程/总时间）最大的路线。请你告诉他这个值。

输入描述 Input Description

第一行包含一个整数n，为小区数。

接下来n*n的矩阵P，其中第i行第j个数表示从小区i到小区j的道路长度为Pi,j。第i行第i个数的元素为0，其余保证为正整数。

接下来n*n的矩阵T，第i行第j个数表示从小区i到小区j需要的时间Ti,j。第i行第i个数的元素为0，其余保证为正整数。

输出描述 Output Description

写入一个实数S，为小区1到达n的最大答案，S精确到小数点后3位。

样例输入 Sample Input

3

0 8 7 

9 0 10 

5 7 0 

0 7 6 

6 0 6 

6 2 0

样例输出 Sample Output

2.125

数据范围及提示 Data Size & Hint

【数据说明】

30%的数据，n<=20

100%的数据，n<=100，p,t<=10000

思路：二分答案+单源最短路（SPFA判负权回路）

代码实现：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=110;
 4 const int maxm=maxn*maxn;
 5 int n,a;
 6 int ns[maxn][maxn],nt[maxn][maxn];
 7 int h[maxn],hs=1;
 8 int e_s[maxm<<2],e_n[maxm<<2];
 9 double e_f[maxm<<2];
10 double l,r,mid,error=1e-4;
11 int s[maxn],q[maxm<<2],head,tail;
12 double d[maxn];
13 bool SPFA(){
14     for(int i=1;i<=n;i++) d[i]=1e8;
15     memset(s,0,sizeof(s));
16     head=tail=0;
17     q[head++]=1,d[1]=0;
18     while(head>tail){
19         a=q[tail++];
20         for(int i=h[a];i;i=e_n[i])
21         if(d[a]+e_f[i]<d[e_s[i]]){
22             d[e_s[i]]=d[a]+e_f[i];
23             q[head++]=e_s[i];
24             ++s[e_s[i]];
25             if(s[e_s[i]]==n) return false;
26         }
27     }
28     return true;
29 }
30 int main(){
31     scanf("%d",&n);
32     for(int i=1;i<=n;i++)
33     for(int j=1;j<=n;j++)
34     scanf("%d",&ns[i][j]);
35     for(int i=1;i<=n;i++)
36     for(int j=1;j<=n;j++)
37     scanf("%d",&nt[i][j]);
38     l=0,r=1e4;
39     while(r-l>error){
40         memset(h,0,sizeof(h)),hs=1;
41         mid=(l+r)/2;
42         for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) ++hs,e_s[hs]=j,e_n[hs]=h[i],e_f[hs]=-ns[i][j]+nt[i][j]*mid,h[i]=hs;
43         if(SPFA()&&d[n]>0) r=mid;
44         else l=mid;
45     }
46     printf("%.3lf",l);
47     return 0;
48 }

不太会判负权回路，我其实过去一直偏向使用Dijkstra。