图论：KM算法

如果，将求二分图的最大匹配的所有匹配边的权重看做1

那么用匈牙利算法求二分图的最大匹配的问题也可以看成求二分图的最大权匹配

如果边权是特例，我们就要使用KM算法来做了

这个算法其实还是比较难的，会用就不错了，更不要说证明了

这里以HDU2255为例，这是一个裸题

在这个题目里面X和Y的size是一样的

然后我们稍微介绍一下这个算法（详细的以后再说吧，目前能力不够）

int n,nx,ny,ans;

int linker[maxn],lx[maxn],ly[maxn],slack[maxn],visx[maxn],visy[maxn];

int G[maxn][maxn];

linker记录的是与当前的下标节点（Y中）相连的X节点，lx和ly是节点顶标，slack是Y定点的松弛量函数

邻接矩阵存储

在这里面，如果有的边不存在，设置权重为0，这样图就可以近似看成一个全连接二分图

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

    {

        lx[i]=-INF;

        for(int j=;j<=ny;j++)

        {

            if(G[i][j]>lx[i]) lx[i]=G[i][j];

        }

    }

首先初始化X中节点的节点顶标

就是对于每一个节点，看其所连接的所有的边，将最大权重设置为X节点顶标

然后呢，就是从每个节点开始进行DFS增广

根据情况修改可行顶标

    for(int x=;x<=nx;x++)

    {

        for(int i=;i<=ny;i++) slack[i]=INF;

        while()

        {

            memset(visx,,sizeof(visx));

            memset(visy,,sizeof(visy));

            if(dfs(x))    break;  //找到增广路，进入下一个点的增广

        //如果失败，需要改变顶标使图中可行边数量增加

        //在所有的增广路的x顶标中减去常数d

        //在所有增广路的Y顶标中增加一个常数d

             int d=INF;

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

                 if(!visy[i]&&d>slack[i])

                     d=slack[i];

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

                 if(visx[i]) lx[i]-=d;

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

                 if(visy[i]) ly[i]+=d;

                 else slack[i]-=d;

        }

    }

然后DFS增广部分如下：

int dfs(int x)

{

    visx[x]=;

    for(int y=;y<=ny;y++)

    {

        if(visy[y]) continue;

        int tmp=lx[x]+ly[y]-G[x][y];

        if(tmp==)

        {

            visy[y]=;

            if(linker[y]==-||dfs(linker[y]))

                {linker[y]=x;return ;}

        }

        else if(slack[y]>tmp) slack[y]=tmp;

    }

    return ;

}

具体原理先鸽了，以后再说

然后给出完整的实现：

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int INF=;

 const int maxn=;

 int n,nx,ny,ans;

 int linker[maxn],lx[maxn],ly[maxn],slack[maxn],visx[maxn],visy[maxn];

 int G[maxn][maxn];

 int dfs(int x)

 {

     visx[x]=;

     for(int y=;y<=ny;y++)

     {

         if(visy[y]) continue;

         int tmp=lx[x]+ly[y]-G[x][y];

         if(tmp==)

         {

             visy[y]=;

             if(linker[y]==-||dfs(linker[y]))

                 {linker[y]=x;return ;}

         }

         else if(slack[y]>tmp) slack[y]=tmp;

     }

     return ;

 }

 int KM()

 {

     memset(linker,-,sizeof(linker));

     memset(ly,,sizeof(ly));

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

     {

         lx[i]=-INF;

         for(int j=;j<=ny;j++)

         {

             if(G[i][j]>lx[i]) lx[i]=G[i][j];

         }

     }

     for(int x=;x<=nx;x++)

     {

         for(int i=;i<=ny;i++) slack[i]=INF;

         while()

         {

             memset(visx,,sizeof(visx));

             memset(visy,,sizeof(visy));

             if(dfs(x))    break;  //找到增广路，进入下一个点的增广

         //如果失败，需要改变顶标使图中可行边数量增加

         //在所有的增广路的x顶标中减去常数d

         //在所有增广路的Y顶标中增加一个常数d

              int d=INF;

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

                  if(!visy[i]&&d>slack[i])

                      d=slack[i];

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

                  if(visx[i]) lx[i]-=d;

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

                  if(visy[i]) ly[i]+=d;

                  else slack[i]-=d;

         }

     }

     int res=;

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

         if(linker[i]!=-)

             res+=G[linker[i]][i];

     return res;

 }

 int main()

 {

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

     {

         nx=ny=n;

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

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

                 scanf("%d",&G[i][j]);

         ans=KM();

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

     }

     return ;

 }

巴特西

图论：KM算法

最新文章

热门文章