首页 > 编程语言 > 详细

匈牙利算法

时间:2017-01-09 22:03:15      阅读:181      评论:0      收藏:0      [点我收藏+]
技术分享
class Hungary {
#define Hungary_MAX_Node 105
#define Hungary_MAX_Edge 10005
public:
    struct EDGE {
        int v;
        int next;
    } edge[Hungary_MAX_Edge];
    int head[Hungary_MAX_Node];
    int Left[Hungary_MAX_Node];
    bool vis[Hungary_MAX_Node];
    int N, M;
    Hungary() {
        clear();
    }
    void clear() {
        N = M = 0;
        memset(Left, 0, sizeof(Left));
        memset(head, -1, sizeof(head));
    }
    void addEdge(int a, int b) {
        edge[M].v = b;
        edge[M].next = head[a];
        head[a] = M++;
    }
    bool dfs(int u) {
        for (int e = head[u]; e != -1; e = edge[e].next) {
            int v = edge[e].v;
            if (!vis[v]) {
                vis[v] = true;
                if (!Left[v] || dfs(Left[v])) {
                    Left[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int Max_Match() {
        int ret = 0;
        for (int i = 1; i <= N; i++) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) {
                ret++;
            }
        }
        return ret;
    }
};
View Code

N:点的数量
M:边的数量
void clear():清空数据结构
void addEdge(int a, int b):添加一条a指向b的匹配
int Max_Match():最大匹配

匈牙利算法

原文:http://www.cnblogs.com/dramstadt/p/6266509.html

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