HDU 2255-奔小康赚大钱（Kuhn-Munkras算法/KM算法-完备匹配下的最大权匹配）

蔚落 2022-07-17 04:07 137阅读 0赞

# 奔小康赚大钱 #

**Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 7423 Accepted Submission(s): 3301**

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

[HDOJ 2008 Summer Exercise（4）- Buffet Dinner][HDOJ 2008 Summer Exercise_4_- Buffet Dinner]

Recommend

lcy | We have carefully selected several similar problems for you: [2063][] [1068][] [3360][] [1083][] [2444][]

模板题~

有个坑阿！！(╯‵□′)╯︵┻━┻

下面这个不能写成\#define 要不然超时超的想哭啊啊啊Ｏ(≧口≦)Ｏ！阿摔(╯' - ')╯︵ ┻━┻

const int maxn = 310;
    const int INF = 0x3f3f3f3f;

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 310;
    const int INF = 0x3f3f3f3f;
    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 = 1; 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(lx,0,sizeof(lx));
        memset(ly,0,sizeof(ly));
        for(int i = 1; i <= nx; i++)
        {
            lx[i] = -INF;
            for(int j = 1; j <= ny; j++)
                if(g[i][j] > lx[i])
                    lx[i] = g[i][j];
        }
        for(int x = 1; x <= nx; x++)
        {
            for(int i = 1; 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 = 1; i <= ny; i++)
                    if(!visy[i] && d > slack[i])
                        d = slack[i];
                for(int i = 1; i <= nx; i++)
                    if(visx[i])
                        lx[i] -= d;
                for(int i = 1; i <= ny; i++)
                {
                    if(visy[i])ly[i] += d;
                    else slack[i] -= d;
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= nx; i++)
            if(linker[i] != -1)
                res += g[linker[i]][i];
        return res;
    }
    int main()
    {
        int n;
        while(scanf("%d",&n) == 1)
        {
            for(int i = 1; i <= n; i++)
                for(int j =1; j <= n; j++)
                    scanf("%d",&g[i][j]);
            nx = ny = n;
            printf("%d\n",KM());
        }
        return 0;
    }
    /**
    2
    100 10
    15 23
    **/

[HDOJ 2008 Summer Exercise_4_- Buffet Dinner]: http://acm.split.hdu.edu.cn/search.php?field=problem&key=HDOJ+2008+Summer+Exercise%A3%A84%A3%A9-+Buffet+Dinner&source=1&searchmode=source
[2063]: http://acm.split.hdu.edu.cn/showproblem.php?pid=2063
[1068]: http://acm.split.hdu.edu.cn/showproblem.php?pid=1068
[3360]: http://acm.split.hdu.edu.cn/showproblem.php?pid=3360
[1083]: http://acm.split.hdu.edu.cn/showproblem.php?pid=1083
[2444]: http://acm.split.hdu.edu.cn/showproblem.php?pid=2444