题目链接：

http://acm.hdu.edu.cn/showproblem.php?

pid=2255

题目大意：

村里要分房子。

有N家老百姓，刚好有N间房子。考虑到每家都要有房住，每家必须分配到一间房子且

仅仅能分配到一间房子。另外， 村长为了得到最大利益，让老百姓对房子进行估价。

比方有3件房子，一

家老百姓能够对第一间出10万，对第二间出2万，对第三间出4万。第二家老百姓能够对第一间出8万，

对第二家出3万，对第三间出5万。那么问题来了：怎么分配，才干使利益最大化。

(村民房子不一定能

分到房，关键看领导分配)。

思路：

建立二分图，一边为N家老百姓，还有一边为N间房子。对老百姓和房子之间估价建立一条有带权边。问

题就转变为了再二分图中找出一个总权值最大的匹配，也就是加权二分图最佳匹配问题。须要用到KM

算法，算法有点复杂，从书上找到一个模板，结果不能执行。。。所以从网上找到一份。

參考博文：http://blog.csdn.net/sdjzujxc/article/details/8604790

AC代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN = 330;

const int INF = 0xffffff0;

int N,NX,NY;

int link[MAXN],lx[MAXN],ly[MAXN],slack[MAXN];

int visx[MAXN],visy[MAXN];

int Map[MAXN][MAXN];

int FindPath(int u)

{

    visx[u] = 1;

    for(int i = 1; i <= NY; ++i)

    {

        if(visy[i])

            continue;

        int temp = lx[u] + ly[i] - Map[u][i];

        if(temp == 0)

        {

            visy[i] = 1;

            if(link[i] == -1 || FindPath(link[i]))

            {

                link[i] = u;

                return 1;

            }

        }

        else if(slack[i] > temp)

            slack[i] = temp;

    }

    return 0;

}

int KM()

{

    memset(ly,0,sizeof(ly));

    memset(link,-1,sizeof(link));

    for(int i = 1; i <= NX; ++i)

    {

        lx[i] = -INF;

        for(int j = 1; j <= NY; ++j)

            if(Map[i][j] > lx[i])

                lx[i] = Map[i][j];

    }

    for(int i = 1; i <= NX; ++i)

    {

        for(int j = 1; j <= NY; ++j)

            slack[j] = INF;

        while(1)

        {

            memset(visx,0,sizeof(visx));

            memset(visy,0,sizeof(visy));

            if(FindPath(i))

                break;

            int d = INF;

            for(int j = 1; j <= NY; ++j)

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

                    d = slack[j];

            for(int j = 1; j <= NX; ++j)

                if(visx[j])

                    lx[j] -= d;

            for(int j = 1; j <= NY; ++j)

                if(visy[j])

                    ly[j] += d;

                else

                    slack[j] -= d;

        }

    }

    int res = 0;

    for(int i = 1; i <= NY; ++i)

        if(link[i] > -1)

            res += Map[link[i]][i];

    return res;

}

int main()

{

    int N;

    while(~scanf("%d",&N))

    {

        NX = NY = N;

        for(int i = 1; i <= N; ++i)

            for(int j = 1; j <= N; ++j)

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

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

    }

    return 0;

}