hungary算法

二分图最大匹配——匈牙利算法

解析

https://blog.csdn.net/sunny_hun/article/details/80627351

代码

bool find(vector<vector<int>>& graph, bool *used, int *couple, int u){
    for(int i=0;i<graph[u].size();i++){
        int v = graph[u][i];
        if(!used[v]){
            used[v] = true;
            if(couple[v]==-1||find(graph, used, couple, couple[v])){
                couple[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary(vector<vector<int>>& graph){
    int n = graph.size();
    bool used[n];
    int couple[n];
    memset(couple, -1, sizeof(couple));
    int cnt = 0;
    for(int i=0;i<n;i++){
        memset(used, false, sizeof(used));
        if(find(graph, used, couple, i)){
            cnt ++;
        }
    }
    return cnt/2;
}