最大流增广路(KM算法) HDOJ 2255 奔小康赚大钱

题目传送门

/*
    KM：裸题第一道，好像就是hungary的升级版，不好理解，写点注释
        KM算法用来解决最大权匹配问题： 在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接Xi，Yj有权w(i,j)，
        求一种匹配使得所有w(i,j)的和最大。也就是最大权匹配一定是完备匹配。如果两边的点数相等则是完美匹配。
        如果点数不相等，其实可以虚拟一些点，使得点数相等，也成为了完美匹配。最大权匹配还可以用最大流去解决
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 3e2 + 10;
const int INF = 0x3f3f3f3f;
int x[MAXN], y[MAXN], w[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
bool visx[MAXN], visy[MAXN];
int n, d;

bool DFS(int u)    {        //hungary算法
    visx[u] = true;
    for (int i=1; i<=n; ++i)    {
        if (x[u] + y[i] == w[u][i] && !visy[i])    {
            visy[i] = true;
            if (ly[i] == -1 || DFS (ly[i]))    {
                ly[i] = u;    return true;
            }
        }
        else if (x[u] + y[i] > w[u][i])    d = min (d, x[u] + y[i] - w[u][i]);        //更新d，贪心思想
    }

    return false;
}

void KM(void)    {
    for (int i=1; i<=n; ++i)    {
        x[i] = 0;
        for (int j=1; j<=n; ++j)    {
            x[i] = max (x[i], w[i][j]);        //初始x标杆为最大值w，y为0
        }
    }

    memset (y, 0, sizeof (y));
    memset (ly, -1, sizeof (ly));
    for (int i=1; i<=n; ++i)    {
        while (true)    {
            memset (visx, false, sizeof (visx));
            memset (visy, false, sizeof (visy));
            d = INF;
            if (DFS (i))    break;            //找到增广轨，退出
            for (int i=1; i<=n; ++i)    {        //没有找到，对标杆进行调整
                if (visx[i])    x[i] -= d;
                if (visy[i])    y[i] += d;
            }
        }
    }

    int res = 0;
    for (int i=1; i<=n; ++i)    {
        res += x[i] + y[i];
    }
    printf ("%d
", res);
}

int main(void)    {        //HDOJ 2255 奔小康赚大钱
    //freopen ("HDOJ_2255.in", "r", stdin);

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

    return 0;
}