WannaflyCamp day1 ：知识盲区就是致命弱点
基本知识点
源点(s)：只出不进的点
汇点(t)：只进不出的点
最大流算法
Edmonds-Karp算法
思想
不断的找BFS增广路，直至不能增广就找到最大流
实现
通过BFS，找出残量网络中的流量，一旦到达终点t立马弹出，通过反向边和BFS记录的路径，修改残量网络的流量，每次用BFS增广保证了路径是最优(即不会出现反悔)
时间复杂度
理论最坏是$(n·m^2)$，但实际上不是很慢
Dinic算法
思想
利用BFS不断求分层图，DFS不断增光求最大流
最大流最小割定理
内容
最大流=最小割
证明
最小费用最大流
概述
在最大流的基础上给每条边加上单位流量的费用cost，在最大流的基础上求最小费用
思想
只要初始流是该流量下的最小费用可行流，每次增广后的新流都是新流量下的最小费用流。
类似Edmonds-Karp算法
但每次用Bellman-Ford算法找增广路而非BFS
思想：对每个点类似的求一个最短路
POJ2135
思路
转化成网络流模型，建立源点s，汇点t。
对于s，s到1建立流量为2，费用为0的边。
对于t，建立n到t流量为2，费用为0的边。
跑最小费用最大流即可
Wannafly day1 Birthday
注意要将费用建在每个区域和t之间才是正确的
最大匹配
二分图最大匹配
概述
注意二分图是不含有奇环的
匈牙利算法
解决二分图最大匹配
邻接表存图的时间复杂度$O(n·m)$
一般图最大匹配
带花树
留坑
最大权完备匹配
概述
即每个点都匹配到
KM算法
权值为正，正常KM
KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。
KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。
最小权完美匹配
概述
即每个点都匹配到
KM算法
权值取反
KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。
KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。
最大权匹配
概述
最大权和即可
KM算法
权值为正，不存在的边赋值为0
KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。
KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。
最小权匹配
KM算法
权值取反，不存在的边赋值为0
一般图最大权匹配
带花树
留坑