有的路，美好的外表下，是危机四伏的阴影。
有的路，走起来很艰难，在剧烈的心痛中，明知路的尽头是绝望却无法回头。
有的路，布满阴霾，伴随着黑暗和孤独，看不清方向。
在路上，我们一边走，一边流泪。
在路上，我们一边走，一边失去。
“你还记得那个地方吗？”
面前的你，闭上眼睛，喃喃着。
“当然，那怎么会忘却呢。$n$ 个记忆碎片的多重空间，每个碎片都有单向道路通往其他碎片。多美的地方”
“那条路呢？从 $S$ 到 $T$ 的路，那条最美好的路呢？你还记得吗？” 你突然看向我。
一阵风吹过，沉默。
我大约知道的，一条路径的美好度是它的长度和通过它的时间的比值。
我确实忘记了，那条路，那条未找到的路，究竟在何方。
过去的过去，还是过去，未来的未来，还是未来么？
请你帮我一次，就一次，好吗。
可是，在这条路上，我能不能遇见你，而你，会不会陪我走完这条路呢？
第一行有三个正整数 $n$，$S$，$T$ 如题意。
接下来有两个 $n \times n$ 的矩阵。
其中第一个矩阵的第 $i$ 行第 $j$ 个数表示从碎片 $i$ 到碎片 $j$ 道路的长度 $s$。
其中第二个矩阵的第 $i$ 行第 $j$ 个数表示从碎片 $i$ 到碎片 $j$ 通过的时间 $t$ 。
保证两个矩阵中第 $i$ 行第 $i$ 个数为 $0$，其余为正整数。
一行一个实数 $k$ 表示最大的美好度，保留三位小数。
对于 $10\% $ 的数据 $n\le 5$。
对于另外 $30\% $ 的数据 $s_{i,j}$ 均相等且 $t_{i,j}$ 均相等（不包括 $i=j$ 的情况）。
对于另外 $20\% $ 的数据，保证最后输出的答案等于一个整数。
对于 $100\% $ 的数据 $n\le 200$, $1\le s_{i,j},t_{i,j}\le 10^5$。
（不得不说出题人文采很不错）
对于 $10\%$ 的数据，枚举每次走的边，暴搜
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #define R register 5 #define MAXN 210 6 #define CMAX(_a,_b) ((_a<_b)&&(_a=_b)) 7 using namespace std; 8 inline int read() 9 { 10 int _a = 0; 11 char ch = getchar(); 12 while(ch>‘9‘||ch<‘0‘) ch = getchar(); 13 while(ch>=‘0‘&&ch<=‘9‘) _a = _a * 10 + ch - ‘0‘, ch = getchar(); 14 return _a; 15 } 16 int W[MAXN][MAXN],C[MAXN][MAXN],S,T,n; 17 int vis[MAXN]; 18 double Ans = 0; 19 void DFS(int u,int w,int c) 20 { 21 vis[u]++; 22 if(vis[u]>2) {vis[u]--;return;} 23 if(u == T) CMAX(Ans,(double)w/c); 24 for(R int i = 1; i <= n; i++) 25 { 26 if(i == u) continue; 27 DFS(i,w+W[u][i],c+C[u][i]); 28 } 29 vis[u]--; 30 } 31 int main() 32 { 33 memset(vis,0,sizeof(vis)); 34 n = read(), S = read(), T = read(); 35 for(R int i = 1; i <= n; i++) 36 for(R int j = 1; j <= n; j++) W[i][j] = read(); 37 for(R int i = 1; i <= n; i++) 38 for(R int j = 1; j <= n; j++) C[i][j] = read(); 39 DFS(S,0,0); 40 printf("%.3lf",Ans); 41 return 0; 42 }
对于 $30\%$ 的数据，输出任意一条边上的 $W/C$
然后讲讲正解吧
考虑过很多算法（$DP$,贪心等），发现似乎很难直接从原图得出答案，考虑二分答案（本来想到过，但是因为不会写小数的二分就。。。）
假如答案为 $Ans$，有 $\sum W - \sum C * Ans = 0$，分解成每条边的权值，即 $W[i] - Ans * C[i]$。
可以使用 $Floyd$ 算出最长路，而且使用该算法比较容易判正环（如出现正环则 $Ans$ 比行），当然 $SPFA$ 亦可
启发：像这种感觉很难直接从原图中获得答案的时候考虑构造答案然后 $check$，而最常用的方式是二分（考场上本来想到的，可是由于是小数然后就。。）
考虑答案与题目的关系，最常见的是构造新图（形象意义上，同P3287（骑行川藏）），通过建模的方式进行 $check$ ，使用图论算法（最短/长路，SCC，BCC，MST）
（似乎图上很少用 DP 的）
AC代码：
1 #include<cstdio> 2 #include<cstring> 3 #define R register 4 #define MAXN 210 5 #define CMAX(_a,_b) ((_a<_b)&&(_a=_b)) 6 const double EPS = 1e-5; 7 using namespace std; 8 inline int read(){ 9 R int _a = 0,_b = 1; 10 char ch = getchar(); 11 while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘)_b=-1;ch=getchar();} 12 while(ch>=‘0‘&&ch<=‘9‘) _a=_a*10+ch-‘0‘,ch=getchar(); 13 return _a*_b; 14 } 15 int n,S,T; 16 int s[MAXN][MAXN],t[MAXN][MAXN]; 17 double Dis[MAXN][MAXN]; 18 inline bool Check(double M) 19 { 20 for(R int i = 1; i <= n; i++) 21 for(R int j = 1; j <= n; j++) 22 Dis[i][j] = (double)s[i][j] - M * t[i][j]; 23 for(R int k = 1; k <= n; k++) 24 for(R int i = 1; i <= n; i++) 25 for(R int j = 1; j <= n; j++) 26 CMAX(Dis[i][j],Dis[i][k]+Dis[k][j]); 27 for(R int i = 1; i <= n; i++) if(Dis[i][i] > 0) return 1; 28 return Dis[S][T] > 0; 29 } 30 int main() 31 { 32 n = read(), S = read(), T = read(); 33 for(R int i = 1; i <= n; i++) 34 for(R int j = 1; j <= n; j++) s[i][j] = read(); 35 for(R int i = 1; i <= n; i++) 36 for(R int j = 1; j <= n; j++) t[i][j] = read(); 37 double L = 0,RR = 100000,Mid; 38 while(RR - L > EPS){ 39 Mid = (L + RR) / 2.0; 40 if(Check(Mid)) L = Mid; 41 else RR = Mid; 42 } 43 printf("%.3lf",L); 44 return 0; 45 }
原文：https://www.cnblogs.com/QuickSilverX/p/10887402.html