首页 > 其他 > 详细

The Hungarian algorithm Template

时间:2014-08-06 14:18:31      阅读:327      评论:0      收藏:0      [点我收藏+]

The Hungarian algorithm with The adjacency matrix :

计算最大匹配问题

int n1, n2, m, ans;
int res[MAXN];
bool vis[MAXN], map[MAXN][MAXN];

void init(){
    int t1, t2;
    memset(map, 0, sizeof(map));
    memset(res, 0, sizeof(res));
    ans = 0;
    scanf("%d%d",&n1,&n2);

    //get map[][]

}
bool find(int a) {
    for (int i = 1; i <= n2; ++i) {
        if (map[a][i] == 1 && !vis[i]) {
            vis[i] = true;
            if (res[i] == 0 || find(res[i])) {
                res[i] = a;
                return true;
            }
        }
    }
    return false;
}
int main() {
    init();
    for (int i = 1; i <= n1; ++i) {
        memset(vis, 0, sizeof(vis));
        if (find(i)) ++ans;
    }
    printf("%d\n",ans);
    return 0;
}    

 

The Hungarian algorithm Template,布布扣,bubuko.com

The Hungarian algorithm Template

原文:http://www.cnblogs.com/wushuaiyi/p/3894133.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!