问答

请问能否使用JS来实现KM算法

作者:admin 2021-09-17 我要评论

如题,使用JavaScript来实现KM算法来解决带权二分图最小匹配 C++实现的代码如下 #include iostream#include cstdio#include memory.h#include algorithm using n...

在说正事之前,我要推荐一个福利:你还在原价购买阿里云、腾讯云、华为云服务器吗?那太亏啦!来这里,新购、升级、续费都打折,能够为您省60%的钱呢!2核4G企业级云服务器低至69元/年,点击进去看看吧>>>)

如题,使用JavaScript来实现KM算法来解决带权二分图最小匹配
C++实现的代码如下

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
 
using namespace std;
 
#define MAX 100
 
int n;
int weight[MAX][MAX];           //权重
int Cx[MAX],Cy[MAX];                //定点标号
bool sx[MAX],sy[MAX];          //记录寻找增广路时点集x,y里的点是否搜索过
int match[MAX];                       //match[i]记录y[i]与x[match[i]]相对应
 
bool search_path(int u) {          //给x[u]找匹配,这个过程和匈牙利匹配是一样的
    sx[u]=true;
    for(int v=0; v<n; v++){
        if(!sy[v] && Cx[u]+Cy[v] == weight[u][v]){
            sy[v]=true;
            if(match[v]==-1 || search_path(match[v])){  //如果第v个y点还没被占,或者第v个y点还可以找到其他可搭配的x点
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
 
int Kuhn_Munkras(bool max_weight){
    if(!max_weight){ //如果求最小匹配,则要将边权取反
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                weight[i][j]=-weight[i][j];
    }
    //初始化顶标,Cx[i]设置为max(weight[i][j] | j=0,..,n-1 ), Cy[i]=0;
    for(int i=0;i<n;i++){
        Cy[i]=0;
        Cx[i]=-0x7fffffff;
        for(int j=0;j<n;j++)
            if(Cx[i]<weight[i][j])
                Cx[i]=weight[i][j];
    }
 
    memset(match,-1,sizeof(match));
    //不断修改顶标,直到找到完备匹配或完美匹配
    for(int u=0;u<n;u++){   //为x里的每一个点找匹配
        while(1){
            memset(sx,0,sizeof(sx));
            memset(sy,0,sizeof(sy));
            if(search_path(u))       //x[u]在相等子图找到了匹配,继续为下一个点找匹配
                break;
            //如果在相等子图里没有找到匹配,就修改顶标,直到找到匹配为止
            //首先找到修改顶标时的增量inc, min(Cx[i] + Cy [i] - weight[i][j],inc);,Cx[i]为搜索过的点,Cy[i]是未搜索过的点,因为现在是要给u找匹配,所以只需要修改找的过程中搜索过的点,增加有可能对u有帮助的边
            int inc=0x7fffffff;
            for(int i=0;i<n;i++)
                if(sx[i])
                    for(int j=0;j<n;j++)
                        if(!sy[j]&&((Cx[i] + Cy [j] - weight[i][j])<inc))
                            inc = Cx[i] + Cy [j] - weight[i][j] ;
            //找到增量后修改顶标,因为sx[i]与sy[j]都为真,则必然符合Cx[i] + Cy [j] =weight[i][j],然后将Cx[i]减inc,Cy[j]加inc不会改变等式,但是原来Cx[i] + Cy [j] !=weight[i][j]即sx[i]与sy[j]最多一个为真,Cx[i] + Cy [j] 就会发生改变,从而符合等式,边也就加入到相等子图中
            for(int i=0;i<n;i++){
                if(sx[i])   //如果点x在S集合里
                    Cx[i]-=inc;
                if(sy[i])   //如果点y在T集合里
                    Cy[i]+=inc;
            }
        }
 
    }
    int sum=0;
    for(int i=0;i<n;i++)
        if(match[i]>=0){
            sum+=weight[match[i]][i];
//            cout << match[i] <<" : "<< weight[match[i]][i] << endl;
        }
    if(!max_weight)
        sum=-sum;
    return sum;
 
 
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&weight[i][j]);
    printf("%d\n",Kuhn_Munkras(1));
    return 0;
}

代码转载自:
https://blog.csdn.net/li13168...

版权声明:本文转载自网络,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。本站转载出于传播更多优秀技术知识之目的,如有侵权请联系QQ/微信:153890879删除

相关文章
  • 请问能否使用JS来实现KM算法

    请问能否使用JS来实现KM算法

  • vant Calendar 日历组件 default-date

    vant Calendar 日历组件 default-date

  • base64_encode_url 与 base64_encode

    base64_encode_url 与 base64_encode

  • angularJS 怎么只刷新table表格信息,

    angularJS 怎么只刷新table表格信息,

腾讯云代理商
海外云服务器