P2868 [USACO07DEC] Sightseeing Cows G 分析

__ryp__ · 2024-02-08 16:55:52 · 个人记录

分数规划，\dfrac{\sum\limits_{u \in S} F_u}{\sum\limits_{e \in E} T_e} \ge c，即 \sum\limits_{u\in S} F_u \ge c\sum\limits_{e\in E} T_e，即 \sum\limits_{u\in S}F_u - c\sum\limits_{e\in E}T_e \ge 0，即 \sum\limits_{e\in E} cT_e - \sum\limits_{u\in S} F_u \le 0

于是就变成判断负环，其中，每一条边 (u,v) 的边权就是 cT_e-F_u。

用 SPFA + 二分可做。