首页 > 代码库 > HDU_2255 二分图最佳完美匹配 KM匈牙利算法

HDU_2255 二分图最佳完美匹配 KM匈牙利算法

2024-07-07 03:24:01   227人阅读

一开始还没看懂这个算法，后来看了陶叔去年的PPT的实例演示才弄懂

用一个lx[]和ly[]来记录X和Y集合中点的权值，有个定理是 lx[i]+ly[j]==w[i][j](边权值) 则该点是最佳匹配，因为首先 那个不等式肯定要>=的，否则就不满足题意了，如果是>则可以去匹配更有价值的边或者把权值降下来让匹配边的潜力更大。

所以只有把握了这个条件，其他就是走一遍最大匹配数。以及up（）函数用来在无法匹配的时候，进行其他点的权值降低（也可以说是增广路的搜索）来得到匹配。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
using namespace std;
int w[N][N],n,lx[N],ly[N],lefts[N];
bool S[N],T[N];
bool dfs(int u)
{
    S[u]=1;
    for (int v=1;v<=n;v++)
    if (lx[u]+ly[v]==w[u][v] && !T[v]){
        T[v]=true;
        if (!lefts[v] || dfs(lefts[v])){
            lefts[v]=u;
            return true;
        }
    }
    return false;
}
void update()
{
    int a=1<<30;
    for (int i=1;i<=n;i++) if (S[i])
    for (int j=1;j<=n;j++) if (!T[j]){
        a=min(a,lx[i]+ly[j]-w[i][j]);
    }
    for (int i=1;i<=n;i++){
        if (S[i]) lx[i]-=a;
        if (T[i]) ly[i]+=a;
    }
}
void KM()
{
    int i,j;
    for (i=1;i<=n;i++){
      lefts[i]=lx[i]=ly[i]=0;
      for (j=1;j<=n;j++){
         lx[i]=max(lx[i],w[i][j]);
      }
    }
    for (i=1;i<=n;i++){
        for (;;){
            memset(S,0,sizeof S);
            memset(T,0,sizeof T);
            if (dfs(i)) break;
            else update();
        }
    }
}
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++) scanf("%d",&w[i][j]);
        memset(lefts,-1,sizeof lefts);
        KM();
        int ans=0;
        for (int i=1;i<=n;i++){
            ans+=lx[i];
            ans+=ly[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

 


联系
我们