练习

网络流

Zero . 二分图 (据说二分图的题都能用网络流跑)

---------理智分析...emm...它们都要找增广路,那网络流和二分图的区别就只是源点和汇点,在二分图左侧和右侧分别建一个源点和汇点即可

• 模板 : 洛谷 二分图匹配
• 洛谷 P2756 飞行员配对方案问题 - 网络流24题
  

I . 最大流算法/一般增广路算法(Dinic & EK)

• 模板 : 洛谷 P3376 【模板】网络最大流
• 洛谷 最小路径覆盖问题 - 网络流24题
• 最开始n个点都是独立的 , 每连一条边 , 就相当于把这个点 ( 所在的链 ) 加到那个点所在的链上 ( 当然最开始还没形成链 ) 作为尾部 ( 有向图 ) ,就用了那个点的路径延伸过来覆盖这个点 , 两条路径转为一条 ==> 所以将多少个点合并了,路径就少多少条 ==> 最小路径覆盖数 = n - 最大流;
• 另外,因为每个点只能指出去一条边,所以源点到该点(在二分图左半的分点)的容量要赋为1,每个点只能接受一条边,所以该点(在二分图右半的分点)到汇点的容量也得赋为1.
• 洛谷 魔术球问题 - 网络流24题
• 洛谷 P2766 最长不下降子序列问题 - 网络流24题
• 洛谷 P4313 文理分科
• 洛谷 P2944 [USACO09MAR]地震损失
• 洛谷 P3410 拍照
• 洛谷 P4174 [NOI2006]最大获利
• 洛谷 P2805 [NOI2009]植物大战僵尸
• 洛谷 P3355 骑士共存问题
• 洛谷 P2402 奶牛隐藏 ( 需二分答案 )
  

II . 最短增广路算法(SAP)

III . 预流推进算法

IV . 最小费用最大流

• 洛谷 P3381 【模板】最小费用最大流
• 洛谷 P4012 深海机器人问题 - 网络流24题
• 洛谷 P4142 洞穴遇险 ( 2018.8.6是rank3 )
• 洛谷 P4016 负载平衡问题 - 网络流24题

$\frac{S-1}{n-1}$