关于匈牙利算法
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/5/9 20:03
  • 上次更新2024/5/9 21:34:26
查看原帖
关于匈牙利算法
745358
ChenZQ楼主2024/5/9 20:03

事情是这样的,我在很久以前听完了y总讲的匈牙利算法,其核心思想就是如果一个点无法匹配,就看前面的点能不能让出来给他匹配。

而最近我又听到了另一种说法,就是说从左点出发,以左右左右的形式构建出一条路径,如果最后能到右,就说明能让匹配数+1

请问哪一种才是真正的匈牙利算法啊,还是说都是,还有哪一种算法跑的更快啊

以下图片分别对应第二种说法和第一种说法

bool find(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=true;            
            if(match[j]==0 || find(match[j])) 
            {
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
2024/5/9 20:03
加载中...