最大权匹配算法（km）

最新推荐文章于 2024-01-02 22:39:24 发布

ruleless

最新推荐文章于 2024-01-02 22:39:24 发布

阅读量1.5k

点赞数

分类专栏：算法文章标签：算法

本文链接：https://blog.csdn.net/ruleless/article/details/7876643

版权

本文深入探讨了二分图中的最大权匹配问题，重点解析了km算法的原理与实现步骤，旨在帮助读者理解和应用这一关键的图论算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

二分图的最大权匹配就是求所有匹配中权值最大的匹配。

char str[105][105];
int node[105][105],w[105][105],n,lx[105],ly[105],link[105];
bool visx[105],visy[105];
bool Find(int a)
{
    visx[a]=true;
    int j;
    for(j=1;j<=n;j++)
    {
        if(!visy[j]&&lx[a]+ly[j]==w[a][j])
        {
            visy[j]=true;
            if(link[j]<0||Find(link[j]))
            {
                link[j]=a;
                return true;
            }
        }
    }
    return false;
}
void km()
{
    int i,j,k;
    memset(link,-1,sizeof(link));
    for(i=1;i<=n;i++)
    {
        ly[i]=0;
        lx[i]=0;
        for(j=1;j<=n;j++)
            lx[i]=max(lx[i],w[i][j]);
    }
    for(k=1;k<=n;k++)
    {
        memset(visx,0,sizeof(visx));
        memset(visy,0,sizeof(visy));
        while(!Find(k))
        {
            int d=1<<30;