学了二分图，整个人都不好了，赶紧趁热打铁敲个日志巩固下记忆。
二分图，就是将一个图分为2个点集后，每个点集内部任意两点之间不存在边，即每一条边都连接在不同点集中的两个点。
匹配，是一个边集，且任两条边不相邻，即不存在公共点。
相关算法：
①最大匹配问题：
顾名思义，就是找到给定图中边数最多的匹配。解决这一问题，可以采用网络流进行构图，或者利用匈牙利算法构造匈牙利树，这
里讨论后一种做法。
显然，空集也是一种匹配，那么我们可以从空集开始，对当前解一步步进行优化，使在满足匹配的前提下，边集尽可能大，或说进行
增广。对于当前匹配，我们可以从一个未覆盖点开始，从这个点的连边进行搜索，直到找到另一个未覆盖点。因起点和终点都是未覆盖
点，所以起始边和终边都是未匹配边，中继点一定是已覆盖点，然后易得知此路径上的边一定是已匹配边和未匹配边交错。要让边集仍
满足匹配，且将起点和终点都被覆盖，只需要把路径上各边都取反，即舍去所有已匹配边，取用所有未匹配边，这时我们便可得到一个
更优解。
考虑对此算法进行优化，假如已某一点为起点无法找到增广路，那么在以后的查找中也不需要考虑该点的增广路，证明的话自己画个
图大概就明白了。
代码如下：
const int MAXN=510; int uN,vN; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u) { int v; for(v=0;v<vN;v++) if(g[u][v]&&!used[v]) { used[v]=true; if(linker[v]==-1||dfs(linker[v])) { linker[v]=u; return true; } } return false; } int hungary() { int res=0; int u; memset(linker,-1,sizeof(linker)); for(u=0;u<uN;u++) { memset(used,0,sizeof(used)); if(dfs(u)) res++; } return res; }
②二分图最大点独立集：
独立集：一个点集，满足其中所以点之间都没有边相邻。
可以证明，二分图最大点独立集点数=总点数-最大匹配边数。证明如下：
对于任意未被匹配的点，假如它们之间有连线，必定存在更优匹配，矛盾。对于已匹配点，由于减去的是边数，我们可以考虑只留下
每条边的其中一个端点，这是可以保证独立。对于一个组未匹配点和已匹配点，如果他们之间存在连线，我们可以把这个已匹配点转为
其匹配点，若该匹配点仍与未匹配点相连，易得到一个更优的匹配解，矛盾，得证。
③最优匹配问题：
原最大匹配问题的变种，所有边都有一个权值，求边权和最大的匹配解。这时需要用到KM算法（全称是Kuhn-Munkras）。
我们可以设二分图中两个点集中的每个点各有一个标记A[i]和B[i]，在整个过程中保证对于边w(i,j)满足A[i]+B[i]≥w(i,j)。假如把所有
A[i]+B[i]=w(i,j)的边组合为一个导出子图，假如这个子图存在完美匹配（即点完全覆盖），那么这个完美匹配一定是原图的最优匹配，但
假如不存在完美匹配，我们需要改变点标记，使更多边进入子图，慢慢使子图存在完美匹配。我们可以设A[i]=maximine(w(i,j))
j∈V，
B[i]=0。当我们找不到完美匹配时，便得到一棵交错树，可以取一个值lack，将A[i]减去lack,B[i]加上lack。此时，对于本已在树中的边或
两顶点都不在树上时，A[i]+B[i]值不变，仍在树中或仍不在树中。对于有一个点在树上，其A[i]+B[i]值增大或减小，那么该边就有可能进
入相等子图，于是子图得到扩大。不断进行该操作，最后可得到一个完美匹配。
代码如下：
const int maxn=20,INF=2147483647; int w[maxn][maxn]; int lx[maxn]={0},ly[maxn]={0}; intl inky[maxn]; int visx[maxn],visy[maxn]; int lack; bool find(intx){ visx[x]=true; for(inty=0;y<maxn;y++){ if(visy[y])continue; int t=lx[x]+ly[y]-w[x][y]; if(t==0){ visy[y]=true; if(linky[y]==-1||find(linky[y])){ linky[y]=x; return true; } } else if(lack>t)lack=t; } return false; } void KM(){ memset(linky,-1,sizeof(linky)); for(inti=0;i<maxn;i++) for(intj=0;j<maxn;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; for(intx=0;x<maxn;x++){ for(;;){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); lack=INF; if(find(x))break; for(inti=0;i<maxn;i++){ if(visx[i])lx[i]-=lack; if(visy[i])ly[i]+=lack; } } } }
原文：http://www.cnblogs.com/Enceladus/p/4979072.html