匈牙利法求二分图的最大匹配

/* g:图的邻接矩阵存储 visited:判断结点是否被访问 v:存储匹配的点 nl,nr:分别为图的右部，左部的结点个数 */ #include <iostream> #include <cstring> using namespace std; const int MAXN = 400; int g[MAXN][MAXN], visited[MAXN], v[MAXN]; int nl,nr; int dfs(int l) { int i; for(i=1; i<=nr; i++) { if(!visited[i] && g[l][i]) { visited[i] = 1; if(-1 == v[i] || dfs(v[i])) { v[i] = l; return 1; } } } return 0; } int Max() { memset(v, -1, sizeof(v)); int ans = 0; for(int i=1; i<=nl; i++) { memset(visited, 0, sizeof(visited)); ans += dfs(i); } return ans; } int main() { //图的录入 int nAns = Max(); return 0; }