http://www.wikioi.com/problem/1183/
分析一下其实很简单的，转换成图论就可以做了。
这个题目是满足二分答案的性质的，因为对于一个答案a，如果a可以，那么比a小的必然也可以。
所以我们先用二分答案去枚举
但是这个二分答案需要注意精度问题，具体是什么呢？
一般二分答案是while(l <= r) if(check(mid)) l = mid + 1; else r = mid - 1;
这样的，愚蠢的我一开始就这样写了，然后精度错误balalalala的
cheeck怎么写呢，有一个p[i]是路程，对于答案ans
满足 你走的路程 / 耗费的时间 = ans
然后就可以根据这个等式去构图，以p[i][j] - t[i][j] * ans为边权，然后求最长路，如果有环这个ans肯定合法，如果没环但是dist[n] >=0 也合法
接下来贴代码
#include <cstdio> #include <algorithm> #include <queue> #include <cstring> #include <cmath> #include <iostream> #define mod 9999973 #define inf 10000000 #define N 105 using namespace std; int n , p[N][N] , t[N][N] , num[N]; bool inq[N]; double map[N][N] , d[N] , sum , sum1; queue <int> q; bool check(double ans) { //构图 memset(map , 0 , sizeof(map)); memset(inq , 0 , sizeof(inq)); while(!q.empty()) q.pop(); for(int i = 1 ; i <= n ; ++i) d[i] = (double)-1e8 , num[i] = 0; for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) { if(i == j) continue; map[i][j] = (double)p[i][j] - (double)t[i][j] * ans; } q.push(1) , inq[1] = 1; d[1] = 0 , ++num[1]; while(!q.empty()) { int po = q.front(); q.pop(); inq[po] = 0; if(num[po] > n) { d[n] = 1e8; break; } for(int i = 1 ; i <= n ; ++i) { if(po == i) continue; if(d[i] < d[po] + map[po][i]) { d[i] = d[po] + map[po][i]; if(!inq[i]) q.push(i) , inq[i] = 1 , ++num[i]; } } } if(d[n] >= 0) return 1; return 0; } void work() { scanf("%d", &n); double l = 0 , r = 0 , mid; for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) scanf("%d", &p[i][j]) , sum += p[i][j]; for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) { scanf("%d", &t[i][j]) , sum1 += t[i][j]; if(p[i][j]) r = max(r , (double)p[i][j] / (double)t[i][j]); } l = sum / sum1; mid = (l + r) / 2; while(1) { if(r - l <= 0.00001) {printf("%.3lf" , mid); break;} if(check(mid)) l = mid; else r = mid; mid = (l + r) / 2; } } int main() { work(); return 0; }