解法
平均の最大化なので，binary search が典型． \(I \subset E\) に対して， $$ f_{I} := \frac{\sum_{i \in I}b_{i}}{\sum_{i \in I}c_{i}} $$ とおく． \(x \in \mathbb{R}\) を固定したとき，\(f_{I} \geq x\) となる \(I\) が存在するか， という判定問題を解けばよい．\(i \in I\) に対して \(w_{i} := b_{i} - c_{i}x\) とおく．
与えられたグラフが DAG なので，このグラフ上で DP が可能． \(i \in V\) に対して，
\(dp_{i} := \) \(0 \rightarrow i\) のパスとなる \(I \subset E\) の取り方のうち， \(\sum_{i \in I} w_{i}\) の最大値
とおく．これは DPで求まる．
注意
Double 型の binary search なので，while を使うよりは， 回数を決めて rep の方が安全．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
rep(i,m){
ll s,t,b,c; cin >> s >> t >> b >> c;
--s, --t;
to[s].emplace_back((Edge){t,b,c});
}
double ok = 0, ng = INFL;
rep(_,150){
double mid = (ok + ng)/2.0;
dp[0] = 0;
rep(i,n){
for(auto ed: to[i]){
chmax(dp[ed.to], dp[i] + ed.b - ed.c*mid);
}
}
if(dp[n-1] >= 0) ok = mid;
else ng = mid;
}
printf("%.10lf", ok);
return 0;
}
