`

hdu 2255 奔小康赚大钱(我的第一个KM匹配)

    博客分类:
  • KM
阅读更多

奔小康赚大钱

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 798    Accepted Submission(s): 362

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

         这题就是最简单的最大权匹配KM算法,直接套用赤裸裸的模板就行了!我做的第一个KM算法,下面就记录一下:

 

 

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define MAXN 305
#define INF 99999999

int w[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
bool sx[MAXN], sy[MAXN];
int pre[MAXN], slack;
int n, m;

int dfs(int u)
{
    sx[u] = true;
    for(int i = 0; i < m; i++)
    {
        if(sy[i]) continue;
        int tp = lx[u] + ly[i] - w[u][i];
        if(!tp)
        {
            sy[i] = true;
            if(pre[i] == -1 || dfs(pre[i]))
            {
                pre[i] = u;
                return 1;
            }
        }
        else if(slack > tp) slack = tp;
    }
    return 0;
}

int KM()
{
    int i, j, k, res;
    memset(pre, -1, sizeof(pre));
    memset(ly, 0, sizeof(ly));
    for(i = 0; i < n; i++)
        for(lx[i]=-INF, j = 0; j < m; j++)
            lx[i] = max(lx[i], w[i][j]);
    for(k = 0; k < n; k++)
    {
        while(1)
        {
            slack = INF;
            memset(sx, false, sizeof(sx));
            memset(sy, false, sizeof(sy));
            if(dfs(k)) break;
            for(i = 0; i < n; i++)
                if(sx[i]) lx[i] -= slack;
            for(i = 0; i < m; i++)
                if(sy[i]) ly[i] += slack;
        }
    }
    res = 0;
    for(i = 0; i < m; i++)
        res += w[pre[i]][i];
    return res;
}

int main()
{
    int i, j, ans;
    while(scanf("%d", &n) != EOF)
    {
        m = n;
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                scanf("%d", &w[i][j]);
        ans = KM();
        printf("%d\n", ans);
    }

    return 0;
}
 

 

0
3
分享到:
评论

相关推荐

    KM匹配题集

    - **【HDU 2255】奔小康赚大钱**:可能需要利用KMP算法解决字符串匹配问题,寻找特定模式的出现次数。 - **【HDU 1533】Going Home**:同样是字符串匹配,可能需要求解最短的匹配长度或找出所有匹配位置。 - **【HDU...

    HDU2013暑期多校联合训练第一场0723-解题报告和标程

    1. "2013暑期多校联合训练第一场0723-解题报告.pdf":这个PDF文件包含了这次训练的解题报告,可能包括了所有题目及其解法的详细分析,对于参赛者来说,这是理解和学习解题策略的重要资源。 2. "2013暑期多校联合训练...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。...ACM HDU 题目分类是一个非常重要的参考资源,对于编程选手来说,掌握这些分类可以帮助他们更好地理解和解决问题。

    2017hdu多校联合训练第一场标程及数据

    【标题】"2017hdu多校联合训练第一场标程及数据"涉及到的是一个编程竞赛的资源集合,主要是针对ACM(国际大学生程序设计竞赛)的比赛训练。这个标题意味着这个压缩包包含了该赛事的官方解决方案(标程)以及用于测试...

    HDU DP动态规划

    例如,一个简单的动态规划问题可以是“斐波那契数列”,其中状态通常定义为第n个斐波那契数,状态转移方程为F(n) = F(n-1) + F(n-2),初始条件为F(0) = 0,F(1) = 1。 在HDU的DP题目中,可能会有各种复杂度的题目,...

    (HDUACM2010版_13)二分匹配及其应用

    杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用

    二分匹配题集

    **匹配**:在一个二分图\( G \)中,存在一个子图\( G' \),若\( G' \)的边集中任意两条边不共用同一个顶点,则称\( G' \)的边集为\( G \)的一个匹配。 **最大匹配**:在所有可能的匹配中,包含边数最多的匹配被称为...

    hdu1250高精度加法

    具体地,题目涉及到了斐波那契数列的一个变种:F(1)=1, F(2)=1, F(3)=1, F(4)=1, F(n&gt;4)=F(n-1)+F(n-2)+F(n-3)+F(n-4),其中n &gt; 4。这里的关键是要能够计算出F(n)的值,而由于这个序列的增长速度非常快,传统的整数...

    HDU题目java实现

    HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案。这里的“java实现”意味着作者使用Java作为编程工具来解答这些算法题。 在Java编程方面,以下是一些可能涵盖的知识点: 1. ...

    二分图的完美匹配 KM算法.docx

    再初始化一个匹配数组`match`,用于记录当前的匹配情况,以及两个辅助数组`xhash`和`yhash`,用于标记顶点状态。 2. 寻找增广路径:通过深度优先搜索(DFS)从未匹配的左部顶点开始,寻找一条可以通过未匹配或已...

    HDU二分匹配及其应用

    HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    ACM HDU

    【标签】"ACM题解 HDU"意味着这是一个关于如何解答HDU ACM题目的资源,可能包含了解题思路、算法解析、代码实现等方面的内容。这样的资料对于准备ACM比赛的选手或者希望提升算法能力的程序员来说非常有价值。 在...

    hdu1290解题报告

    **第一步:线分割平面** 首先解决较为简单的二维情况,即如何用 _n_ 条直线分割一个平面,并求出最多可以将平面分割成多少部分。这里的关键在于理解每新增一条直线都会增加新的分割区域数。 - 对于第 _1_ 条直线,...

    HDU图论题目分类

    HDU图论题目分类提供了一个系统化的图论知识框架,帮助开发者和研究者更好地理解和掌握图论的基本概念和技术。 以下是HDU图论题目分类中的部分知识点: 1. 图的基本概念:图的定义、图的表示、图的遍历、图的搜索...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu1001解题报告

    hdu1001解题报告

    HDU1059的代码

    HDU1059的代码

Global site tag (gtag.js) - Google Analytics