模板 KM算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了模板 KM算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含990字，纯文字阅读大概需要2分钟。

内容图文

KM算法计算带权二分图最优匹配
时间复杂度\(O(n^3)\)
模板题：hdu2255 奔小康赚大钱

const int maxn=310;
const int inf=0x3f3f3f3f;

int n;
int g[maxn][maxn],ex1[maxn],ex2[maxn],match[maxn],slack[maxn];    
bool vis1[maxn],vis2[maxn];

bool dfs(int x){
    vis1[x]=true;
    for(int y=0;y<n;y++) {
        if(vis2[y]) continue; 
        int gap=ex1[x]+ex2[y]-g[x][y];
        if(gap==0){  
            vis2[y]=true;
            if(match[y]==-1 || dfs(match[y])){   
                match[y]=x;
                return true;
            }
        } 
        else{
            slack[y]=min(slack[y],gap);  
        }
    }
    return false;
}

int KM(){
    memset(match,-1,sizeof(match));    
    memset(ex2,0,sizeof(ex2));  
    for(int i=0;i<n;i++) {
        ex1[i]=g[i][0];
        for(int j=0;j<n;j++) {
            ex1[i]=max(ex1[i],g[i][j]);
        }
    }
    for (int i=0;i<n;i++) {
        memset(slack,0x3f,sizeof(slack));    
        while(1){
            memset(vis1,false,sizeof(vis1));
            memset(vis2,false,sizeof(vis2));
            if(dfs(i)) break;
            int d=inf;
            for (int j=0;j<n;j++)
                if(!vis2[j]) d=min(d,slack[j]);
            for (int j=0;j<n;j++){
                if(vis1[j]) ex1[j]-=d;
                if(vis2[j]) ex2[j]+=d;
                else slack[j]-=d;
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)
        res+=g[match[i]][i];
    return res;
}

内容总结

以上是互联网集市为您收集整理的模板 KM算法全部内容，希望文章能够帮你解决模板 KM算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---