Hdu2255 奔小康赚大钱（二分图最大权匹配KM算法）

时间：2023-03-08 19:56:19
Hdu2255 奔小康赚大钱（二分图最大权匹配KM算法）

奔小康赚大钱

Problem Description
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).
Input
输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。
Output
请对每组数据输出最大的收入值，每组的输出占一行。
Sample Input
2
100 10
15 23
Sample Output
123
Source

——————————————————————————————————

题目的意思是时候每个人要买一栋房子，房子数和人数相等，问最大总花费多少？

思路：二分图最大权匹配

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <climits>

using namespace std;

#define LL long long

const int MAXN = 505;

const int INF = (1<<31)-1;

int g[MAXN][MAXN];

int lx[MAXN],ly[MAXN]; //顶标

int linky[MAXN];

int visx[MAXN],visy[MAXN];

int slack[MAXN];

int nx,ny;

bool find(int x)

{

    visx[x] = true;

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

    {

        if(visy[y])

            continue;

        int t = lx[x] + ly[y] - g[x][y];

        if(t==0)

        {

            visy[y] = true;

            if(linky[y]==-1 || find(linky[y]))

            {

                linky[y] = x;

                return true;        //找到增广轨

            }

        }

        else if(slack[y] > t)

            slack[y] = t;

    }

    return false;                   //没有找到增广轨（说明顶点x没有对应的匹配，与完备匹配(相等子图的完备匹配)不符）

}

int KM()                //返回最优匹配的值

{

    int i,j;

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

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

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

        for(j = 0,lx[i] = -INF; j < ny; j++)

                lx[i] = max(lx[i],g[i][j]);

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

    {

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

            slack[i] = INF;

        while(true)

        {

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

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

            if(find(x))                     //找到增广轨，退出

                break;

            int d = INF;

            for(i = 0; i < ny; i++)          //没找到，对l做调整(这会增加相等子图的边)，重新找

            {

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

                    d = slack[i];

            }

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

            {

                if(visx[i])

                    lx[i] -= d;

            }

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

            {

                if(visy[i])

                     ly[i] += d;

                else

                     slack[i] -= d;

            }

        }

    }

    int result = 0;

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

    if(linky[i]>-1)

        result += g[linky[i]][i];

    return result;

}

int main()

{

  int n;;

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

  {

   nx=ny=n;

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

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

    {

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

    }

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

  }

    return 0;

}

　　

相关文章