新网络流 24 题

题单介绍

因为旧的网络流 24 题已经跟不上时代了,于是打算整理一份所谓新网络流 24 题。 前置知识:网络最大流,最大流最小割定理,网络费用流,线性规划基本知识,hall 定理(CF1009G),dilworth 定理(P4298),最小割树(CF343E)。 update 20240304 删除了 P3488,新增 CF1009G 作为 hall 定理的模板题。 update 20240314 删除了 P2304,新增 agc038f 作为一个帅气的建模儿题,因为我们不要码农提,所以无限之环也不要。 update 20240317 作者终于把这个题单 AK 了,顺便按照个人觉得的难度顺序大致排了一下。 update 20240321 作者本人写的题解。[题解](https://www.luogu.com.cn/article/0e75ggrn)

题目列表

  • 飞行员配对方案问题
  • 餐巾计划问题
  • 最小路径覆盖问题
  • [AHOI2014/JSOI2014] 支线剧情
  • [国家集训队] happiness
  • [CTSC1999] 家园 / 星际转移问题
  • T'ill It's Over
  • Allowed Letters
  • [NOI2008] 志愿者招募
  • [JDWOI-1] 蜀道难
  • [NOI2012] 美食节
  • [ZJOI2013] 防守战线
  • [六省联考 2017] 寿司餐厅
  • [NOI2009] 植物大战僵尸
  • [BJWC2018] Kakuro
  • [CQOI2017] 老C的方块
  • Pumping Stations
  • [CTSC2008] 祭祀
  • [WC2007] 剪刀石头布
  • [北京省选集训2019] 图的难题
  • [ARC161F] Everywhere is Sparser than Whole (Judge)
  • Showing Off
  • [AGC038F] Two Permutations
  • [ZJOI2011] 营救皮卡丘