点击打开链接

最大权匹配

KM算法

算法步骤：

设顶点Xi的顶标为a[i]，顶点Yi的顶标为b[i]

ⅰ.初始时，a[i]为与Xi相关联的边的最大权值，b[j]=0，保证a[i]+b[j]>=w(i,j)成立

ⅱ.当相等子图中不包含完备匹配时，就适当修改顶标以扩大相等子图，直到找到完备匹配为止

ⅲ.修改顶标的方法

当从Xi寻找交错路失败后，得到一棵交错树，它的所有叶子节点都是X节点，对交错树中X顶点的顶标减少d值，Y顶点的顶标增加d值，对于图中所有的边(i,j)，

可以看到：

i和j都不在交错树中，边(i,j)仍然不属于相等子图  

i和j都在交错树中，边(i,j)仍然属于相等子图

i不在交错树中，j在交错树中，a[i]+b[j]扩大，边(i,j)不属于相等子图

i在交错树,j不在交错树中,边(i,j)有可能加入到相等子图中

为了使a[i]+b[j]>=w(i,j)始终成立,且至少有一条边加入到相等子图中,d=min{a[i]+b[j]-w(i,j)},i在交错树中,j不在交错树中

时间复杂度:需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时枚举边来求d值，复杂度为O(n2),总的复杂度为O(n4).简单优化可以降低到O(n3),每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果不在相等子图中，则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#define for0(a,b) for(a=0;a<b;++a)
#define for1(a,b) for(a=1;a<=b;++a)
#define foru(i,a,b) for(i=a;i<=b;++i)
#define ford(i,a,b) for(i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int maxn = 310;
const int INF = 1e9;
/*KM算法
 *O(nx*nx*ny)
 *求最大权匹配
 *若求最小权匹配，可将权值取相反数，结果再取相反数。
 */
int nx, ny;
int g[maxn][maxn];
int linker[maxn], lx[maxn], ly[maxn];//y中各点匹配状态,x,y中的顶标
int slack[maxn];
bool visx[maxn], visy[maxn];

bool DFS(int x)
{
    visx[x] = true;
    for(int y=0; y<ny; ++y){
        if(visy[y]) continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if(tmp == 0){
            visy[y] = true;
            if(linker[y] == -1 || DFS(linker[y])){
                linker[y] = x;
                return true;
            }
        }
        else if(slack[y]> tmp)
            slack[y] = tmp;
    }
    return false;
}

int KM()
{
    memset(linker, -1, sizeof linker );
    memset(ly, 0, sizeof ly );
    for(int i=0; i<nx; ++i){
        lx[i] = - INF;
        for(int j=0; j<ny; ++j)
            if(g[i][j]> lx[i])
                lx[i] = g[i][j];
    }
    for(int x=0; x<nx; ++x)
    {
        for(int i=0; i<ny; ++i)
            slack[i] = INF;
        while(true)
        {
            memset(visx, false, sizeof visx );
            memset(visy, false, sizeof visy );
            if(DFS(x)) break;
            int d = INF;
            for(int i=0; i<ny; ++i)
                if(!visy[i] && d>slack[i])
                    d = slack[i];
            for(int i=0; i<nx; ++i)
                if(visx[i])
                    lx[i] -= d;
            for(int i=0; i<ny; ++i)
            {
                if(visy[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
    int res = 0;
    for(int i=0; i<ny; ++i)
        if(linker[i] != -1)
            res += g[linker[i]][i];
    return res;
}

//HDU 2255
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    freopen("out.cpp", "w", stdout);
#endif // ONLINE_JUDGE
    int n;
    while(~scanf("%d", &n))
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                scanf("%d", &g[i][j]);
        nx = ny = n;
        printf("%d\n" ,KM());
    }
    return 0;
}

hdu2255 奔小康赚大钱，最大权匹配，KM算法