分数规划+费用流：LibreOJ - 2003
分数规划+费用流：LibreOJ - 2003
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075828
https://vj.imken.moe/contest/598718#problem/H
一坨分数的东西，显然二分，然后移一下项，可得 ，然后要选择一组最大匹配满足
根据霍尔定理必然存在匹配，所以我们直接跑费用流即可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-19
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080431 https://vj.imken.moe/contest/598718#problem/K 三元环数量尽量多，也就是非三元环数量尽可能少。非三元环的充要条件是存在一个点度数为2，而每条边可以给一个点一个度数，然后就变成了经典网络流问题。 但是，对于一个点，我们还是无法求最少流。考虑转化为费用流。一个点向汇点连很多条边，分别代表着度数为1...
2023-12-19
阴阳反转——运用INF巧妙建网络流：P3980
阴阳反转——运用INF巧妙建网络流：P3980 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080814 https://vj.imken.moe/contest/598718#problem/L 考虑一个奇妙的转化： 有很多 inf\infinf 个人要走 nnn 扇门，第 iii 扇只能走 infa−i\inf_a-iinfa−i 个人，有 mmm 个通道，可以把一个人从 sis_isi 运到 ti+1t_i+1ti+1 ，但要给 c...
2023-12-19
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075877 https://vj.imken.moe/contest/598718#problem/J 观察到数据范围很小，但一个很重要的信息我们缺失了，就是珠宝的数量，所以我们考虑枚举珠宝的数量 kkk 。 对于横纵坐标什么至多至少的限制，比如 aia_iai 前最多偷 bib_ibi 个，可以转化为第 [bi+1,k][b_i+1,k]...
2023-09-03
分数问题善用移项：0902T2
分数问题善用移项：0902T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647332 其实就是分数规划，但不完全是。 对于求 ∑pili∑li\Large\frac{\sum p_il_i}{\sum l_i}∑li∑pili 在限定条件下的最大值，此类问题可以考虑 二分答案 并 移项 。 ∑pili∑li≥k\Large\frac{\sum p_il_i}{\sum l_i}\ge k ∑li∑pili≥k ∑pili≥k∑li...
2023-12-18
有顺序多匹配的网络流——每个人已经不一样了：P2053
有顺序多匹配的网络流——每个人已经不一样了：P2053 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070777 https://vj.imken.moe/contest/598718#problem/G 每个人可以修多辆车，但我们要想成，修第二辆车时，这个人已经不是原先那个人了。 所以对于每个师傅，拆成修倒数第一个、倒数第二个时的他，然后跑费用流 即可。