匈牙利算法

说明

匈牙利算法的DFS实现

g[][]两边顶点的划分情况

优点:适用于稠密图,DFS找增广路,实现简洁易于理解

时间复杂度:O(VE)

使用方法

  1. 给vN和uN赋值,uN是匹配左边的顶点数,vN是匹配右边的顶点数
  2. memset(g, 0, sizeof(g));
  3. g[u][v]=1表示加一条从u指向v的边,注意单向加边
  4. int ans = hungary(); 得到最大匹配数

Tips

注意下标!

const int maxn=1000;
int uN,vN;  //u,v数目
int g[maxn][maxn];//编号是1~n的
int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
    int v;
    for(v=1;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=1;u<=uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    }
    return res;
}

results matching ""

    No results matching ""