前言：
网络流核心在于建图，于是就有了这篇博客。
目录：
$1.~$网络流基础题
$2.~$网络流24题选做
$3.~$费用流乱七八糟的选做
$4.$一些奇技淫巧的建图
$1.~$网络流基础
模板就不讲了，详见上回模板小结。
入门题还是$USACO$的毒瘤题吧，没啥技巧。
[USACO4.4]追查坏牛奶Pollutant Control
最小割板子+对于割边集的边数询问。由于不要求输出边集所以较为简单。
首先学了网络流的都知道，并非满流就在最小割上，但不满流一定不在。于是直接再建一个图，若当前满流就设为1，否则设为0，再跑一边网络流流，此时的最小割就是割边数。
[USACO5.4]奶牛的电信Telecowmunication
这题应该放在建图那块，但这个算基本操作所以谈不上奇技淫巧。
用到的是拆点的思想。
拆点顾名思义，就是把“点”拆成“点--边--点”的形式，边的权值由具体题目而定。
当然通过拆点，我们就可以将无向图转换为有向图来跑网络流啦。我们将原点$A$拆成$A_1$和$A_2$，其中$A_1$为入边点，负责连接所有的入边；同理，$A_2$负责连接所有出边，从入边到出边连一条大小为点值的边，此题点值为1。
然后就是裸的网络流。
三。。三分图？？
类似二分图那样建三次边，跑个最大流就没了。。
$2.~$网络流24题选做
好题啊！！
参照题解
口胡题解
易想到超源为地球，超汇为月球，太空站为中间节点，船为连边。
但是由于船是动态变化的，不能只存一张静态图就跑。经题解发现分层图可以很好解决这一问题。
分层图是将不同状态的图通过分层，在各个状态图中求他们的子问题。在这题里，我们按照时间分层，可以得到这两种连边方案。
- 不进行太空船移动，这个时刻停留此节点，不限流。
- 如果有太空船，则转移到下一层图的下一节点，容量为最大载人数。
然后超源给每点连边，每过一层就跑他的残量网络，若总流大于K就符合答案。
分层图也可做一些其他题感受一下。。
裸的二分图，学匈牙利时候写的，现在想想$Dinic$万能那为啥学匈牙利。。
最大权独立子图的基本应用，参照题解
怎么还是二分图。。干脆改名成二分图24题算了
超级源点连题目，题目连边到种类，种类连边到超级汇点顺便带上自己的权值。如果最大流=要出题的数量，就暴力搜索题目与类型连边中满流的边。
核心是 在DAG中，最小边覆盖=点总数-最大匹配，于是将每个点都拆成入点和出点，连成一个二分图跑Dinic就行。。
同上题，参照题解
第一题打出一个辅助DP，根据DP结果拆点，连边，乱搞就没了，构造并不难想。。。
第二简单的题。。因为取了一个数上下左右就不能取，发现可以黑白染色，于是发现可以建个二分图。。
然后抄题解看到一个重要性质：
（二分图）最大独立集 = 点权和 - 最大权匹配/最小点覆盖数
最大独立集：点集中任意两点没有公共边。
最大权匹配：就是带权的最大匹配，可类比最大流
最小点覆盖数：用最少的点覆盖所有边，可类比最小割。
于是类比最大流最小割定理，有个König定理：最小点覆盖=最大匹配。不同的是这东西不知道咋证明。。
于是就直接按照二分图跑网络流的方法建图，不同的是每个白点对应的有4个黑点（上下左右），还有加一个超级源点那里加个权值。
和试题库问题如出一辙。
与方格取数两倍经验。题目给的图已经充分证明他也可以黑白染色，所以他也是二分图（雾）
于是把读入的连边改成八个方向就过了。
同下，就是拆点的不同运用。。
- 对于第一个条件：在点的地方限流即可
- 对于第二个条件：在点的地方不限流即可
- 对于第三个。。：点和边都不限流即可。
费用均为点权。
裸的费用流，没啥讲头。
$3.~$费用流乱七八糟的选做
由于加了一维变量，费用流难度会明显高于网络流（吧）。
所以从做的题目中选三四道总结一下，找找感觉。。
【HDU2255】【费用流】奔小康赚大钱
这貌似是本博客第一道洛谷上找不到的题，想着总是要先讲讲类似板子的题吧。。
这题是一个经典图论的输入，我们可以把人和房子建成二分图，然后人与房子连<1,g[i][j]>的边（表示流量1，费用g[i][j])。
然后裸的跑就行了。。
[NOI2012]美食节
[ZJOI2010]网络扩容
题面描述：
求网络的最大流，且给你每个边的扩容费用，问扩容K的流量要多少钱？
口胡题解：
求完第一问的残量网络不要扔,裹上鸡蛋液,粘上面包糠,下锅炸至金黄，隔壁小孩馋哭啦 。因为里面虽然已经不能在流了，但可以通过扩容后面的边从而使残量网络再次利用。
我们每条边再连一个<INF,F[I]>的边，在终点限个流即可。
[SDOI2010]星际竞速
题面描述：
赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发，访问这N颗行星每颗恰好一次，首先完成这一目标的人获得胜利。
由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。
天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。
尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。
口胡题解：
这题可以看出来是个最小边覆盖，但是由于要满足费用最小所以严格来说是个最小边权覆盖(龇牙)。
还是按照最小边覆盖来建立二分图，费用也顺便连了，本来想从超源连边到各个出点但这明显是不懂最小边覆盖建立二分图意义的表现。
二分图中的所有出点所连向的入点，仅仅表示在图上该点连向的后继，并不代表此点是否为边的起始点。
然后我们发现，如果右边点集（入点的集合）没有流量经过，说明此点没有前驱。也就是他一定是起始点，所以我们从超源连边向每个点的入点，费用为跳到这个点的费用即可。
$4.~$一些奇技淫巧的建图
这PART估计没机会怎么写了，可能以后看到网络流好题都会加进去吧。。
[NOI2009]植物大战僵尸
我乔鲁诺·天泽龟有一个梦想，那就是A遍以我玩过游戏命名或番剧命名的题目！
那你一辈子A不掉星露谷物语了。
题目描述：
太长了不念了。
分析：
这题的难点，仅仅是建图！建图！！建图！！！
第一张图：
超源连向所有行的右手第一格，然后按顺序连接格子，由于不是最终建图所以没有边权，点权是当前的能源价值，最后连到超汇。
当然，可能点对之间存在保护关系，于是从保护方向被保护方连边。
第二张图：
我们发现这个DAG里出现本该没有的自环，我们可以知道原本子环内以及子环后可以到的点现在都到不了了，因为如果要到达就必须经过那个环，而环内植物可以两两保护。。
于是我们就可以缩点了，别惊讶，缩点是图论里的重要算法，这正体现了本题极高的综合性。
缩完点我们可以利用深搜来标记子环及子环后的点（除超汇），把他们通过打标记给删掉。
第三张图：
如果你要吃了某个植物，那首先你要把保护它的所有植物吃掉才行，这让你想到啥？
没错，最大权独立子图的定义即是如此。
于是我们把边全部反向，按照求最大权独立子图的方案建图（正点权连超源，负点权连超汇，原本边无限流），然后跑完直接正点权和-最小割即可。
值得一提的是，原来的超源和超汇作为点权为0的点，仍要作为原来图的一部分参与网络流。
然后就没啦！
网络流大概就到这里了，希望过了几个月别把板子给忘了。。