夢に僕らで帆を張って
来るべき日のために夜を超え

标签 0/1分数规划 下的文章

October 31, 2019

洛谷P1768 天路

题意最优比率环数据范围:$1 \le n \le 7000,1 \le m \le 20000$题解$0/1$分数规划要求$$ans=\frac{\sum_i^{i \in E} v_i}{\sum_i^{i \in E} p_i}$$二分这个答案$mid$,将每条边的边更改为$$mid \cdot p_i-v_i$$跑负环即可代码:#include<iostream> #in...
September 26, 2019

0/1分数规划

0/1分数规划一、分数规划给出若干二元组 $(v_i,c_i)$ ,要求从中选出一些,使得 $\frac{\sum v_i}{\sum c_i}$ 最大(最小)。二、解法先考虑最大,最小同理。1、二分法假设问题的最优解为 $ans$ ,则有$$\frac{\sum v_i}{\sum c_i} \le ans$$移项$$\sum v_i \le ans \cdot \sum c_i$$$$\...