有顺序多匹配的网络流——每个人已经不一样了：P2053
有顺序多匹配的网络流——每个人已经不一样了：P2053
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070777
https://vj.imken.moe/contest/598718#problem/G
每个人可以修多辆车，但我们要想成，修第二辆车时，这个人已经不是原先那个人了。
所以对于每个师傅，拆成修倒数第一个、倒数第二个时的他，然后跑费用流 即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-19
分数规划+费用流：LibreOJ - 2003
分数规划+费用流：LibreOJ - 2003 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075828 https://vj.imken.moe/contest/598718#problem/H 一坨分数的东西，显然二分，然后移一下项，可得 ci=ai−kbic_i=a_i-kb_ici=ai−kbi ，然后要选择一组最大匹配满足 ∑ci≥0\sum c_i\ge 0∑ci≥0 根据霍尔定理必然存在匹配，所以我们直接跑费用流即可
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-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...