2013-team4/code/hungary

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
匈牙利算法
不区分两侧的点，全部点个数为 n，编号从 1 开始
}}}
{{{
const int N = 2005;

struct Hungary{
    int match[N];
    bool vis[N];
    vector<int> G[N];
    int n, col[N];
    // 全图共 n 个顶点
    void init(int n){
        this->n = n;
        for(int i = 1; i <= n; i++) G[i].clear();
    }
    // 添加边
    void add_edge(int a, int b){
        G[a].push_back(b);
        G[b].push_back(a);
    }
    // 以下两个函数求最大匹配
    bool dfs(int x){
        vis[x] = true;
        for(int i = 0; i < G[x].size(); i++){
            int y = G[x][i], z = match[y];
            vis[y] = true;
            if(z < 0 || !vis[z] && dfs(z)){
                match[x] = y; match[y] = x;
                return true;
            }
        }
        return false;
    }
    // 返回最大匹配，匹配的顶点在 match[i] 中，没有为 -1
    int max_matching(){
        int ret = 0;
        memset(match, -1, sizeof(match));
        for(int i = 1; i <= n; i++){
            if(match[i] < 0){
                memset(vis, 0, sizeof(vis));
                if(dfs(i)) ret++;
            }
        }
        return ret;
    }
    // 以下两个函数求解最大独立集和最小顶点覆盖
    // 用 0 或 1 染色，区分开两个集合
    void color(){
        for(int i = 1; i <= n; i++){
            if(i <= r) col[i] = 0;
            else col[i] = 1;
        }
    }
    // 构造最小顶点覆盖或最大独立集，返回数组长度
    int solve(int *arr){
        max_matching();
        color();
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
            if(col[i] == 0 && match[i] == -1)
                dfs(i);
        int p = 0;
        for(int i = 1; i <= n; i++){
            if(col[i] == 0 && !vis[i] || col[i] == 1 && vis[i]){
                // 最小顶点覆盖
                arr[p++] = i;
            }
            else{
                // 最大独立集
                //arr[p++] = i;
            }
        }
        return p;
    }
};
}}}

匈牙利算法
不区分两侧的点，全部点个数为 n，编号从 1 开始

const int N = 2005;
struct Hungary{
    int match[N];
    bool vis[N];
    vector<int> G[N];
    int n, col[N];
    // 全图共 n 个顶点
    void init(int n){
        this->n = n;
        for(int i = 1; i <= n; i++) G[i].clear();
    }
    // 添加边
    void add_edge(int a, int b){
        G[a].push_back(b);
        G[b].push_back(a);
    }
    // 以下两个函数求最大匹配
    bool dfs(int x){
        vis[x] = true;
        for(int i = 0; i < G[x].size(); i++){
            int y = G[x][i], z = match[y];
            vis[y] = true;
            if(z < 0 || !vis[z] && dfs(z)){
                match[x] = y; match[y] = x;
                return true;
            }
        }
        return false;
    }
    // 返回最大匹配，匹配的顶点在 match[i] 中，没有为 -1
    int max_matching(){
        int ret = 0;
        memset(match, -1, sizeof(match));
        for(int i = 1; i <= n; i++){
            if(match[i] < 0){
                memset(vis, 0, sizeof(vis));
                if(dfs(i)) ret++;
            }
        }
        return ret;
    }
    // 以下两个函数求解最大独立集和最小顶点覆盖
    // 用 0 或 1 染色，区分开两个集合
    void color(){
        for(int i = 1; i <= n; i++){
            if(i <= r) col[i] = 0;
            else col[i] = 1;
        }
    }
    // 构造最小顶点覆盖或最大独立集，返回数组长度
    int solve(int *arr){
        max_matching();
        color();
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
            if(col[i] == 0 && match[i] == -1)
                dfs(i);
        int p = 0;
        for(int i = 1; i <= n; i++){
            if(col[i] == 0 && !vis[i] || col[i] == 1 && vis[i]){
                // 最小顶点覆盖
                arr[p++] = i;
            }
            else{
                // 最大独立集
                //arr[p++] = i;
            }
        }
        return p;
    }
};