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

点击打开链接

最大权匹配

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;

}