转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081198472074/
二分图，是图论中的一个经典模型，关于二分图，涉及了很多问题，比如最大匹配，最优匹配，完美匹配，最小覆盖。网络流也是这样，再求最大匹配的时候，实际上可以利用转化的思路，就像利用最短路算法求解差分约束系统，利用单源最短路求单目标最短路，利用单源最大流求多源最大流，都是利用了转换的思想，将一个不熟悉的问题转换或者规约为一个熟知的问题。
再比如如果可以把很多问题可以规约到最大流，便可以证明该问题存在多项式时间算法。
对于二分图最大匹配，经典的算法是匈牙利算法，主要利用增广路求最大匹配。
详细介绍请参考：
http://imlazy.ycool.com/post.1603708.html
http://hi.baidu.com/deking/blog/item/74c61a6d2eb7c2fe4316941e.html
大体介绍一下：
增广路的定义(也称增广轨或交错轨)：
若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
由增广路的定义可以推出下述三个结论：
1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2－P经过取反操作可以得到一个更大的匹配M’。
3－M为G的最大匹配当且仅当不存在相对于M的增广路径。
用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)
算法轮廓：
(1)置M为空
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径为止
时间复杂度 邻接矩阵：最坏为O(n^3) 邻接表：O(nm)
空间复杂度 O(n^2) O(m+n)
这里用网络流求最大匹配，参考题目poj3401 asteroids ,二者本质上是相同的。
这可以通过一点修改，在最大流网络中，加一条S与T之间的路，然后观察最大流每次发现的增广路径实际上通过，这条路全部连起来了，而再观察比较匈牙利算法中的增广路，应该得出实际上它们本质是一个，最大流中的增广实际上也是匈牙利中的增广。
网络流模型，首先需要定义流网络，实际上是由一些节点，及节点间的流量限制组成的一个图。在一个流网络中，节点u，v间的流量限制我们用C(u,v)表示，所有的C(u,v)>=0。对于一个网络，网络中的节点可能不存在边，这样，这样的C(u,v)=0。另外网络中具有两个特殊的点，源点和出点。
模型的目标，是求可以流过该网络的最大流量。
最基本的方法是Ford-Fulkerson，该方法主要借助了三个概念，其中剩余网络，和增广路主要用于计算最大流的过程中。而最小cut，则主要为了证明该方法的正确性。
基本框架是：
Ford-Fulkerson(G,s,t)
init flow f to 0
while there exist a 增广路 p
沿着增广路，对流进行增加
return f
利用最大流求最大匹配：
只需要增加一个s和T即可，同时增加S到各点的C(s,i) = 1,和各点到T的C(i,T) = 1.
基本步骤和实现方式如下：
1.
构图，对于图(注意是有向图)的表示可以使用vector <vector<Edge>> G,保存，其中G[i]保存了i的所有以i为起点的边，且该边上C值>0,对于边(u,v)来说，只要C(u,v)或者C(v,u)任意一个大于0，我们就要把u-v,v-u作为边保存到G中，否则不保存.保存的目的，是为了方便后面进行BFS，这样不需要遍历所有顶点，只要看邻接表即可。
而该边上关于该边C的信息可以保存在一个二维数组，也可以保存在Edge结构中。注意：对于某些
2.
初始化，Cf(u,v) = C(u,v),当具有一条有向边(u,v)时C(u,v) = 1,否则C(u,v) = 0,所有的f(u,v)=0.（注意这里的C，f均是一个二维数组，保存了所以u，v对的信息,并非单独针对具有边的那些顶点对）。
3.
寻找增广路，主要是利用Cf(u,v)信息，寻找一条从S到T的路径，在这条路上，所有的Cf(u,v)均大于0.
如果增广路存在，进行4.
否则结束。
4.
沿着增广路，更新流f，和网络容量C，这里要根据你的剩余网络的表示方式，如果你只用一个C数组保存，就要保证当前C减去的是该增广路上C(u,v)的最小值min_c,如果我们用两个数组，分别保存了原始的C和剩余网络的C。则只需要用原始网络的减去当前流f。公式如下
对于增广路上的所有边(u,v),进行如下,更新流f，求剩余网络C：假设分别采用两个数组保存原始的C和剩余网络的C
f(u,v) = f(u,v)+C(u,v)
f(v,u) = 0 – f(u,v)
Cf(u,v) = C(u,v) – f(u,v)
Cf(v,u) = C(v,u)-f(v,u)
回到3.
注：
第一次写，犯了不少错误。。。
1.
注意所有的C(u,v)>=0 ,但是f(u,v)有的<0 ,这样在求剩余网络的时候，一开始只是简单的把，增广路径上的路径的C(u,v)设成了。实际上漏掉了那些f(u,v)<0的，对于这些，它们的c(u,v)更新之后实际上是大于0的。
如图1，如果沿着红色线路走，应当得到图3的剩余网络，而不是图2的。
图1
图2
图3
2. 实际上，虽然bfs之前，将s的父亲设成s，在不断的更新过程中s的父亲是变化的，这样下面利用temp != nodes[temp].parent就无法结束了，导致内存溢出而结束。应该改为temp != s。
vector <int > path;
int temp = t;
while(temp != nodes[temp].parent){
path.push_back(temp);
temp = nodes[temp].parent;//lost it.
}
path.push_back(temp);
3.注意bfs过程中，由于C的更新，可能具有环，导致死循环，这样要求bfs过程中需要设一个bool数组，标记已经访问的节点，避免重复访问。
4.对于min_c最好实际计算，而不是想当然的认为是1.
5.在求剩余网络的时候，我实际采用的是一个数组不断保存Cf，但是更新的时候，减的是截至到目前已经积累的流f，这样当然是不正确的，应该用
f[u][v] += min_c;
f[v][u] = 0 – f[u][v];
c[u][v] = c[u][v] – min_c;
c[v][u] = c[v][u] + min_c;
6.还有一些小错误，就是比如忘了更新temp
temp = nodes[temp].parent;//lost it.
u，v的值一开始取颠倒了
int u = path[i];
int v = path[i-1];// u and v exchanged.
当然最严重的错误，还是没有搞清楚求剩余网络的过程，忽略了那些f(v,u)小于0的部分。