二分图匹配（匈牙利算法
DFS
实现）
| INIT: g[][]
邻接矩阵
;
| CALL: res =
MaxMatch
();
|
优点：实现简洁容易理解，适用于稠密图，
DFS
找增广路快。
|
找一条增广路的复杂度为
O
（
E
），最多找
V
条增广路，故时间复杂度为
O
（
VE
）
\*==================================================*/
const int MAXN = 1000;
int uN, vN; // u, v
数目，要初始化！！！
bool g[MAXN][MAXN]; // g[i][j]
表示
xi
与
yj
相连
int xM[MAXN], yM[MAXN]; //
输出量
bool chk[MAXN]; //
辅助量检查某轮
y[v]
是否被
check
bool SearchPath(int u){
int v;
for(v = 0; v < vN; v++)
if(g[u][v] && !chk[v])
{
chk[v] = true;
if(yM[v] == -1 || SearchPath(yM[v]))
{
yM[v] = u; xM[u] = v;
return true ;
}
}
return false ;
}
int MaxMatch(){
int u, ret = 0 ;
memset(xM, -1, sizeof (xM));
memset(yM, -1, sizeof (yM));
for(u = 0; u < uN; u++)
if(xM[u] == -1){
memset(chk, false, sizeof (chk));
if(SearchPath(u)) ret++;
}
return ret;
}