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

一开始还没看懂这个算法，后来看了陶叔去年的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]=;

    for (int v=;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=<<;

    for (int i=;i<=n;i++) if (S[i])

    for (int j=;j<=n;j++) if (!T[j]){

        a=min(a,lx[i]+ly[j]-w[i][j]);

    }

    for (int i=;i<=n;i++){

        if (S[i]) lx[i]-=a;

        if (T[i]) ly[i]+=a;

    }

}

void KM()

{

    int i,j;

    for (i=;i<=n;i++){

      lefts[i]=lx[i]=ly[i]=;

      for (j=;j<=n;j++){

         lx[i]=max(lx[i],w[i][j]);

      }

    }

    for (i=;i<=n;i++){

        for (;;){

            memset(S,,sizeof S);

            memset(T,,sizeof T);

            if (dfs(i)) break;

            else update();

        }

    }

}

int main()

{

    while (scanf("%d",&n)!=EOF)

    {

        for (int i=;i<=n;i++)

            for (int j=;j<=n;j++) scanf("%d",&w[i][j]);

        memset(lefts,-,sizeof lefts);

        KM();

        int ans=;

        for (int i=;i<=n;i++){

            ans+=lx[i];

            ans+=ly[i];

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

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

最新文章

热门文章