新网络流 24 题

因为旧的网络流 24 题已经跟不上时代了,于是打算整理一份所谓新网络流 24 题。

前置知识:网络最大流,最大流最小割定理,网络费用流,线性规划基本知识,hall 定理(CF1009G),dilworth 定理(P4298),最小割树(CF343E)。

update 20240304

删除了 P3488,新增 CF1009G 作为 hall 定理的模板题。

update 20240314

删除了 P2304,新增 agc038f 作为一个帅气的建模儿题,因为我们不要码农提,所以无限之环也不要。

update 20240317

作者终于把这个题单 AK 了,顺便按照个人觉得的难度顺序大致排了一下。

update 20240321

作者本人写的题解。题解


  1. P2756 - 飞行员配对方案问题
  2. P1251 - 餐巾计划问题
  3. P2764 - 最小路径覆盖问题
  4. P4043 - [AHOI2014/JSOI2014] 支线剧情
  5. P1646 - [国家集训队] happiness
  6. P2754 - [CTSC1999] 家园 / 星际转移问题
  7. P5029 - T'ill It's Over
  8. CF1009G - Allowed Letters
  9. P3980 - [NOI2008] 志愿者招募
  10. P7730 - [JDWOI-1] 蜀道难
  11. P2050 - [NOI2012] 美食节
  12. P3337 - [ZJOI2013] 防守战线
  13. P3749 - [六省联考 2017] 寿司餐厅
  14. P2805 - [NOI2009] 植物大战僵尸
  15. P4486 - [BJWC2018] Kakuro
  16. P3756 - [CQOI2017] 老C的方块
  17. CF343E - Pumping Stations
  18. P4298 - [CTSC2008] 祭祀
  19. P4249 - [WC2007] 剪刀石头布
  20. P5295 - [北京省选集训2019] 图的难题
  21. AT_arc161_f - [ARC161F] Everywhere is Sparser than Whole (Judge)
  22. CF1416F - Showing Off
  23. AT_agc038_f - [AGC038F] Two Permutations
  24. P4542 - [ZJOI2011] 营救皮卡丘