奔小康赚大钱
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
Sample Output
这题就是最简单的最大权匹配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;
}
分享到:
相关推荐
HDU2013暑期多校联合训练第一场0723-解题报告和标程
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
2017hdu多校联合训练第一场标程及数据
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码