匈牙利二分匹配

发表于 更新于 分类于 阅读次数：

    关于算法的说明，可以参看这个大牛的讲解，很详细： http://imlazy.ycool.com/post.1603708.html 直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool find(int s)
{
    for (int i=1;i<=n;i++)//从1到n编号
    {
         if (map[s][i] && !visit[i])
        {
            visit[i]=1;
            if (pre[i]==0 || find(pre[i]))
             {
                 pre[i]=s;
                 return true;      
             }
    }
    return false;
}

int hungary()//返回最大匹配数
{
     int ans=0;
     for (int i=1;i<=n;i++)
     {
        memset(visit,0,sizeof(visit));
        if (find(i)) ans++;
     }
     return ans;
}

  好吧，具体的代码就应该是这样了，但是二分图是无向图吧。。。有向图，怎么破…