算是康复福利了，以前没做过，但是实际是非常水的题目，应该可以作为入门题了
诡异的是 这道题description莫名奇妙没了。
题意：
两个人从 1 -> n ，每条路径最多走两次，走第一次为 d ，走第二次为 d+a ，问最短的路径。
思路：
对于一组数据，建两次边即可。容量为1，花费分别为 d ， d + a。
源点流入1 容量为 2 ， 花费 0
n流入汇点 容量 2 ，花费 0
注： 给定的边为有向边
AC code
#include
康复计划之 最小费用最大流
以前写的是直接在网上拿了一个模板，直接套了A……
这次好好在纸上模拟了一下，理解了一下。
最小费用最大流的增广路算法简单说就是不断求最短路(因为残量网络和反向边的存在)，记录最短路，再进行流量处理，直到最后不存在通路，则停止。
下面是一个 入门题
题意：
给你一张图，要你从1 -> n 再从 n -> 1 不能走重复的路径。问你最短方案。
思路：
其实就是找出最短和次短的 1 -> n 的路径，当然路径不允许任何重叠。
单纯的两次spfa是不可行的。因为第一次最短路很可能会把通路断掉。
AC Code
#include
一眼题，但是有个很坑的地方，我看了题目没注意。
就是输入数据会有无效输入……结果贡献了3发wa，还不断尝试开大数组……
传送门
题意：
给你一张无向图，让你从1点出发，经过2点，最后到3点，能否实现。每个点只能去一次。
思路：
肯定是拆点啦，容量设置成1即可。再从2开始跑，看流量能否为2。
AC Code
#include
貌似是卡spfa的，但薛昊说slf优化一下也可以过
个人感觉写的非常崩溃……用数组实现队列的时候是WA，stl实现就是tle，我觉得这很可能是空间上的问题。因为最近数组大小开错不停wa不停tle的情况太多了……
看很多题解都是dijkstra实现的。改了一下直接A了
题意：
美团初赛城市群的原题……上次没写出来，碰到原题真的是内心崩溃。
简单说，在一张图的基础上，每个节点都会属于一个 “ 层 ” ，每个相邻的 “ 层 ” 中的节点都相互可达，问 1 到 n 的最短距离。
思路：
对 “ 层 ” 建立源点与汇点，对于每个层里面的每个点，源点到点 ，点到汇点的距离各为 0 。再对 “ 层 ” 之间建边，点之间建边跑最短路即可。
AC Code
#include
康复计划 之 ida*
题意：
这种玩具要你操作最少次数且操作字典序最小，使得中间的8个数字相同。
思路：
迭代加深 启发式 搜索
估价函数采用 8 – 中间数字最多的数字数量
因为每次操作如果想达到最终结果，一次最多只能转化出一个，如 aaab ，一次转化出两个的话，中间那个必定不相同，可以自己在纸上试试。
这道题本身在深搜层数上并不会很大，ida * 的优势就体现了出来。
AC Code
#include
康复计划之搜索 1
因为有个小学弟在第二天就说ida * 看不懂，搞得我挺慌 我可以说我也不是很熟么
题意：
经典八数码
思路：
这里提供的是单向bfs + 打表思路，本来想复习ida * 但是不小心看到了kuangbin的思路，就写了一下。
简单说就是我从起始状态 123456780 开始对0进行bfs，通过康托展开的hash函数进行记录状态和路径。询问时对哈希值进行询问和查找。
实际上并没有用到康托展开的性质，只是通过2进制hash而已……
#include
又是一些细节问题…… 如果以我现在的水平去现场赛写网络流的题目，就算我会建图，我觉得还是挺悬的。 这里提前简单说一下dinic算法的最低上限的情况。 dinic的最高上限是 O ( ( V^2 E ) ) ，这是谁都知道的，然而对于一些特殊的图还有一些更低的上限。 在具有单位容量的网络中，Dinic算法可以在更短的时间内输出结果。每条阻塞流可以在 O ( E ) 的时间内构建，并且阶段的数量不超过 O( ( \sqrt E ) )或 O ( ( \sqrt[3] { V ^ 2 } ) )。此时算法的复杂度为 O ( ( min { ( \sqrt E , \sqrt[3] { V ^ 2 } ) } ) E )。 在二分图匹配问题的网络中，阶段的数量不超过 O ( ( \sqrt V ) )，算法的时间复杂度不超过 O ( ( \sqrt V E ) )。这种算法又被叫做Hopcroft-Karp算法。更普遍的情况是，…
kuangbin把这道题的难度设置为 crazy …… 搞得我都不太敢刷……
题意：
混合图中欧拉回路的判定
思路：
这道题是真的不好想，最后还是去看了题解，因为比较典型 好吧是我菜
混合图欧拉回路无法用普通的定理去判定，不行可以试试……网络流建模给出的思想是将无向边任意转化成有向边，再去通过变换无向边的方向来实现欧拉回路。
建图方式：
* 对无向边建立你所设定的方向，容量为1
* 对于每个点，如果入度与出度差的绝对值为奇数，则不存在欧拉回路。 （ 因为反转一条边，则两个点的入度出度差各自变化 2 ）
* 否则 ，对于每个点如果 入度>出度 则为 汇点，与超级汇点容量为 ( 入度 – 出度 ) / 2 ，反之则为源点，与超级源点容量为 ( 出度 – 入度 ) / 2 。
跑一遍dinic即可。
残余网络中流量不为0的边即为反转边。这样求出欧拉路径也不算什么难事了。
#include