匈牙利算法的两种实现:
1.DFS找增广路
#include
#include
using namespace std;
const int MAXN = 100;
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;
int 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;
}
优点:实现简洁,容易理解,适用于边比较多的图,DFS找增广路快。
2.BFS找增广路
#include
#include
using namespace std;
#define MAXN 128
int g[MAXN][MAXN], Mx[MAXN], My[MAXN], Nx, Ny;
int chk[MAXN], Q[MAXN], prev[MAXN];
int MaxMatch(void)
{
int res = 0;
int qs, qe;
memset(Mx, -1, sizeof(Mx));
memset(My, -1, sizeof(My));
memset(chk, -1, sizeof(chk));
for (int i = 0; i < Nx; i++)
{
if (Mx[i] == -1)
{
qs = qe = 0;
Q[qe++] = i;
prev[i] = -1;
bool flag = 0;
while (qs < qe && !flag)
{
int u = Q[qs];
for (int v = 0; v < Ny && !flag; v++)
{
if (g[u][v] && chk[v] != i)
{
chk[v] = i;
Q[qe++] = My[v];
if (My[v] >= 0)
prev[My[v]] = u;
else
{
flag = 1;
int d = u, e = v;
while (d != -1)
{
int t = Mx[d];
Mx[d] = e;
My[e] = d;
d = prev[d];
e = t;
}
}
}
}
qs++;
}
if (Mx[i] != -1)
res++;
}
}
return res;
}
优点:适用于稀疏二分图,边较少,增广路较短。