网络流题目详讲+题单(入门版)(持续更新中......)

图论——网络流
PS：如果你觉得你早已入门，可以去提高版看一看

写在前面的话(潦草)

• 这篇博客不会讲定义，理解啊什么的，那些知识点网络上......仅仅是题目详讲
  但是每一道题的题解和知识点还是会涵盖的(笔者做一道更一次)
• 建议使用博客右边的主题切换，换成夜间模式可能看起来更舒服(随性)
• 笔者根据自己的感受(也有一定参考性的)给题目编了个难度，有主观色彩，可以根据实际需要来选择

前置知识点：

PS:自行与后面的题目最大匹配

• ☆洛谷网络最大流 || 题解
• ☆洛谷二分图匹配 || 题解
• ☆☆洛谷最小费用最大流 || 题解
• ☆当前弧优化了解一下谢谢(不难，只是需要代码我就不想讲)
• ☆☆最大权闭合子图(定义自己找)==正权点和-最小割(最大流)

一些题目(记得这里是入门版)：

PS:若无特殊说明，均为luogu上的题目，难度有标记

网络最大流/一般增广路(Dinic&EK)

模板题不讲

• ☆草地排水(最大流)
• ☆地震逃生(最大流)(判断最大流是否为0，为0则说明所有学生都跑不出去，其他直接算)

转变最小割

• ☆小M的作物(最小割)

  1. 最大流==最小割
  2. 显然这道题所有的收益加起来减掉最小割就是答案
  3. 考虑建边：把所有作物向A连一条a[i]的边，向B了连一条b[i]的边；集合另开两个点，一个向A连一条c1[i]的边，另一个向B连一条c2[i]的边，最后把两个点分别向集合内所有点连边(都是有向边)，暴力跑Dinic就ojbk

• ☆奶牛的电信(最小割)(注意一下这里的最小割是点)

• ☆狼抓兔子(最大流最小割问题)

  1. 嗯，用最少的狼堵住路让所有兔子都过不去......这也太明显了吧
     
     • 全部堵住——割
     • 用最少的狼——最小割
     • 最小割==最大流
  2. 没错我们做完了，敲板子去吧(连边也很**就不多讲了)

小专题

为什么要裂点？

可能做网络流的题目会有疑问，到底什么时候应该把同样的两个点拆成两个来做呢，个人认为这道题可以完美地回答：当你需要以某种方式制约自己但是这种制约又不能通过别人的制约来实现时(很抽象，没事看题)

• ☆☆教辅的组成(最大流)

  • 开始讲题：
    
    1. 拆点：三种教辅——四列点(中间一样的两列(原因见后))，课本肯定放中间(影想两种)
    2. 建图：
       ①源点向第一列所有点连边，第四列所有点向汇点连边(容量肯定是1啊)
       ②课本第二列和第三列连容量为1的边，看那些书有联系确定就连边
       ③为什么课本一定要列成两列点呢？嗯，首先课本只能用一次对吧，但是只能用一次又不能通过练习册和答案书来连边决定(看着上面那段话)，所以我们只能考虑自己与自己连一条容量为1的边来保证只用一次了......
    3. Dinic跑一遍OK
  • 现在应该理解那段话的意思了吧！嗯，这些都是很妙的思(tao)想(lu)

• ☆☆酒店之王

  • 和教辅的组成基本一模一样(就连边的输入有一点差别)，所以就不多讲了......

• ☆☆吃饭

  • 也是相当简单，我只是把这类题放一起而已

带点小小小技(困)巧(难)

• ☆☆蜥蜴(最大流)

  想到方法并不难

  1. 拆点(先别问为什么......)：把矩阵都变成点，变成两列点
  2. 怎么建图：
     
     • ① 把源点向初始有蜥蜴的地方连边(当然费用为1)；把能跳出去的有柱子的地方向汇点连边(好吧前面都是废话，谁都知道)
     • ② 考虑题目说从哪根柱子离开才有损害，所以拆点成两列的作用出来了，(先别疑问为什么，自然懂)，从自己向另一列点的自己连边，然后考虑可以跳到的点，从第二列的那个点向第一列的自己连边，原因就是因为要保证从这里出去一定要减流量还不能损害到别的柱子(有点抽象，自己思考一下，真的不难的)
  3. 最大流板子

• ☆☆地震损失2

  • 不难，网络流的正常套路跑最小割(自己连自己，其余按边连)
  • 注意处理一下报告的地方流量正无穷，其余流量为1

• ☆☆魔术球问题(网络流24题)(贪心/最大流)

  介绍两种方法(因为我们学信息又不是只会网络流就行了Q_Q)

  • 第一种——贪心
    
    1. 看到题目第一眼有没有一种感觉，能放就放！
    2. 具体来说就是我放在之前的管子上面总会比新开一个管子放球更优，所以直接枚举所有已经放过的管子，看是否可以放下，放不了就新开管子放....很简单吧
    3. 啥？你问我证明？cjoier告诉你：大胆猜想，不用证明，证明就是你再写个dfs拍一下个数就行了。。。溜了溜了
  • 第二种——网络流
    首先我们考虑如何建图，即表达相邻球之间的关系。
    
    1. 首先一个不难想到的东西：柱子数一定关于球数单调递增。
    2. 可以将一个球拆点为A和B，先从源点S向A连容量为1的边，从B向汇点连容量为1的边。
    3. 对于能够与i和为完全平方数的球j，连接Aj和Bi来体现出它们可以在一个管子里相邻
    4. 不停地加球：球数每增加1就建立新加入的球的关系，并且重复地跑最大流。
       我们这样可以求出某一柱子数下最多能放置的球数，因为当新加入的球能够加入柱子时，重复跑最大流是能得到新流(该球可与其他球构成新的相邻关系)的，只要一直能得到新流，就说明柱子上还可以再加。
    5. 不停加柱子：跑完所有的柱子就到答案了。
       当有一次得不到新流，就说明柱子满了，新加入的球并没能加入到任何一个柱子上。此时我们就加柱子(从源点引流到这个球上)。直到柱子加到超过n，此时的球数-1就是最大球数(因为此时实际上柱子加到超过n了)。
    6. 考虑输出答案：①记下第一个加入柱子的球。②在DFS得到增广路的过程中，总是记下该点连接的下一个点的球的编号，形成类似链表的结构。③输出再取出第一个加入柱子的球，来遍历它所在的那条链。(和前面的那题最短路径覆盖差不多)

最大权闭合子图

• 拍照
• 太空飞行计划问题(网络流24题)
  

  • 这两个题基本一样，就是跑最大权闭合子图，不是很难，知道套路就行
    
  • 对于这两个题的套路：
    
    1. 源点连向有利润的(容量为利润)，要花钱的连向汇点(容量为花费)，中间连关系(容量Inf)
       PS： 其实我也不大知道为什么这么连边，但是别人就是对的，我也有一些玄学的理解。。。这里就不讲了，怕教坏大家。。。
       
    2. 重中之重：最大权闭合子图的最大利润=正权利润-最小割(最大流)

  
  

二分图匹配(匈牙利)

基本都是板子(笑哭.jpg)

• ☆飞行员配对方案问题(网络流24题)
  (match数组记录的就是匹配到的人，枚举输出就ok(我的板子用的match数组))
• ☆CJOJ寻找代表元
• ☆假期的宿舍
  

  1. 是不是二分图匹配的题目都这么裸(jian dan)
     
  2. 连边代表i可以睡j+n的床，然后暴力跑匈牙利
     
  3. 几个值得注(fei)意(hua)的地方：
     
     • 我不在学校住就不能去占床位(不往外连边)
       
     • 我是外校的就没有初始床位......
       
     • 这个题是多组数据，记得初(bie)始(nao)化(can)......(我还因此爆了一次0......)
     
     

费用流

个人认为费用流都有些难度(虽然这里是入门版)

• ☆☆负载平衡问题(网络流24题)

  • 这道题显然可以当均分纸牌加强版来贪心nlogn做，这里就不详讲了(洛谷的题解第一篇的讲的挺好，虽然标签是网络流)
  • 好了，网络流的做法，虽然没有贪心优秀，但是可以练网络流嘛
    
    1. 首先运输完之后肯定每个地方值都为开始各个地方的平均数对吧(又没有运到别的地方去......)，那么我们直接拿原来的值减掉平均数变成一串有正有负的数
    2. 显然正负的意义是是否运出去(放到网络流里：正就是源点多给了我，我要送走(建边跑啊)，负就是得多给汇点一些东西保证收支平衡对吧，显然)
    3. 完了，这就上面一讲也没什么好写的了，边都建完了......//滑稽
    4. 开始暴力跑最小费用最大流......没了

• ☆☆晨跑

  1. 首先一眼看出不就是个最小费用最大流吗
  2. 连边和前面的蜥蜴有点像：①先把除1,n之外的点裂成两个，再自己和另一列的自己连；②如果两点u，v有道路，则把第二列的u连向v(理由也和蜥蜴一样)；③如果和1有边，则从1连过来(n同理)
  3. 所以再套个板子就ojbk了(1-->n的情况就直接连，不用多想)

• ☆☆☆海机器人问题(网络流24题)

  1. 看到数据范围这么小，但又不能暴力搞，看这一个标本只能被采一次，不是典型的网络流题目吗，标本有费用？那就最大费用最大流(名字瞎编的)
  2. 网络流最难的地方：建图
     
     • 考虑矩阵中的点只能往两个方向动，且有收益(费用)，肯定要连边，所以输入的时候就把这些边全部连起来，需要注意：①输入的方法有些毒瘤；②一个点可以经过多次，但费用只可以被使用一次，那么先连一条容量为1，费用为收益的边，再连一条容量Inf，费用为0的边，显然可以解决这个问题；③第二次南北方向的收益的输入，边连的点之间相差的是Q是(因为是上下)
     • 然后只有a个点有一些机器人进来，b个点有一些机器人出去，所以(这个不难)把源点与那a个点连边，容量为进入的机器人数(b那边连边类推)
  3. 很高兴地告诉你，剩下的只有板子了(这不废话)，但别忘了SPFA跑最长路，因为是求最大收益(费用)，或者可以把费用手动改成负然后跑最短路，最后再负回来就行了。
  4. 可以看看代码......

总结

这里为刚入网络流这个坑的同学们总结一下

• 网络流中最大流是考的最多的，但往往也是比较容易想到的(放狗屁)，虽然有些题目它的正解建边十分复杂难想，但是是相对而言的。这之中最大权闭合子图也是许多地方爱考的(毕竟基于最大流，但是又要难想很多)
• 其次考的多的就是费用流了，复杂多样，各种花里胡哨的考法，反正抓住一点：图建出来了其他都不是事(又在天真了)，对，没错，网络流的所有难点就只有建边了(对大多数人而言//鄙夷)
• 至于二分图，它本身就是最大流的一个特殊版本，其实我们根本不必把它放进来......基本都比较水吧。。。也有难题，但也是主要考连边啊什么的

那么如果上面的题目实在是太水了，可以前往我的网络流题目详讲提高版看看