知识点

网络流

推荐学习博客 (基本覆盖网络流算法,讲解详细。 建议 : 细读博主所写,略读其引用的概念,理解其代码)
Ps : 这篇博客的"当前弧优化Dinic算法"是错的(正确版本看Tyher的，我的也行)
Tyher的 、 我的
我的代码有点注释辅助理解

Attention !!!

Dinic 过程、要点简述

• 每次bfs寻找一条增广路(即流量还能往上涨的路) ;
• 在bfs找残余流量大于0的路(并建分层图)时，只要第一次到达终点就停止,因为只要depth[]大于0了就不会再被扩展到，继续遍历的话只是浪费时间;
• 一次bfs找到的路可能可以跑多次dfs;
• 每次dfs，都记录一下走到每个节点的哪条出边了 ( 即用cur[]数组代替head[]数组 (我的代码中head[]数组名为record[]数组)。 );

二分图

• 二分图的点分布在两个无交集合X,Y中 , 同个集合的点互相无边相连
• 判断一个图是否为二分图 :
  选一个点开始bfs,第一个点标号为1,它扩展出的点标号为2,接下来依次扩展到未被标记过的点,编号都是父亲编号+1 ( 就用1,2其实也行 ) , 最后查找所有边 ( bfs中未被经过的边也要查 ) ,若每条边的端点都是一奇一偶,它就是二分图
  Ps : 多个联通块时 , 每个联通块都得是二分图
  
  
  
• 二分图匹配 & 最大匹配 ( 理解性知识点,不赘述 )
• attention!! 二分图匹配中任意边无交点!
  
• 据说二分图的题都能用网络流跑 :
• ---------理智分析...emm...它们都要找增广路,那网络流和二分图的区别就只是源点和汇点,在二分图左侧和右侧分别建一个源点和汇点即可
• 从而有 : 二分图的最大匹配数 就是 建了源汇点之后的最大流!

网络流 连边小技巧

• 如果想限制经过一个点的次数 , 可以把它拆成两个点 , 中间连上容量为期望次数的边 , 然后把入边全部连到左边的点 , 出边都由右边的点发出 , 形成一个类似桥的东西

最小费用最大流 ( 参考博客 ( 博客中甚至将SPFA转化成了dijktra ) )

用SPFA找增广路 , 以cost(单位流量的费用)为关键字每次跑最短路并算出这条路的总费用 , 直到跑出最大流 ( 再无增广路 ) , 各路径总费用的和即最小费用 .