分数规划，拓扑排序
Beautiful Path
题目链接:https://atcoder.jp/contests/abc324/tasks/abc324_f
题意:给定一个有向无环简单图，每条边有两个属性,$cost,value$。要求选若干条边，组成一条点1到点n的路径，使得$\frac{\Sigma value_i}{\Sigma cost_i} $最大化。题目保证存在至少一条点1到点n的路径。其中$n,m \in[1,2e5]$
$cost,value\in[1,2e3]$
分析:题目要求式子的形式很明显提示了分数规划的思路。选取一个答案，并且判断答案是否可行，二分缩小规模得到最终答案。
图中找一条路径的要求可以转化为取边时存在之前状态的依赖，但更简单的想法是将图中的边重新赋权，由于DAG的特性，直接拓扑排序遍历全图，最后判断终点处权值是否非负。