题意：

---

给定一张有向图，每个点有权值 \(fun[i]\) ，每条边有权值 \(time[i]\)

要求找出一个环，使得环上所有点的点权和除以所有边的边权和最大

解：

---

首先，显然，这是一道01分数规划题

参照分数规划的套路

假定当前二分的值为 \(mid\) ，有环 \(S=(\{v\},\ \{e\})\) ，环有 \(t\) 个点和 \(t\) 条边

考虑是否存在 \(S\) 使得

\[\sum_{i=1}^{t}(mid*time_{i}-fun_{i})<0 \\ 即\quad\exists S=(\{v\},\ \{e\})\quad使得\quad mid<\frac{\sum_{i=1}^{t}fun_{i}}{\sum_{i=1}^{t}time_{i}} \]

此时答案应该大于 \(mid\)

若不存在这样的 \(S\) ，则

\[\forall S,\quad mid\geqslant \frac{\sum_{i=1}^{t}fun_{i}}{\sum_{i=1}^{t}time_{i}} \]

此时答案应该小于等于 \(mid\)

问题又来了，如何判断是否存在 \(S\) ？

有这样的办法：

在每次选定 \(mid\) 之后

新建一个与原图一样的图，但是没有点权，只有边权，并对边权值做如下修改

\(\forall e_{i}=edge(x\ ->\ y),\quad weight(x\ ->\ y)=mid*time_{e_{i}}-fun_{x}\)

这样建图有什么好处？

这样，若要判定 \(\sum_{i=1}^{t}(mid*time_{i}-fun_{i})<0\) ，刚好对应图中存在“负环”

由此，在新建的图上跑SPFA，有负环说明 \(mid<\frac{\sum_{i=1}^{t}fun_{i}}{\sum_{i=1}^{t}time_{i}}\)

没有则说明 \(mid\geqslant \frac{\sum_{i=1}^{t}fun_{i}}{\sum_{i=1}^{t}time_{i}}\)