HDU - 2255 奔小康赚大钱 （二分图的最佳完美匹配）
奔小康赚大钱Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13366 Accepted Submission(s): 5827 Problem Description 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。
Input 输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。
Output 请对每组数据输出最大的收入值，每组的输出占一行。
Sample Input 2 100 10 15 23
Sample Output 123
Source |
有n个人，n栋房子，每个人对每个房子有不同的出价，问最优的分配方式使输入最大。便是一道二分图最佳完美匹配的模板题~~。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 350;
int n, m;
int G[maxn][maxn], use[maxn], lx[maxn], ly[maxn];
int slack[maxn];
bool visx[maxn], visy[maxn];
bool DFS(int x) {
visx[x] = 1;
for (int y = 0; y < m; y++) {
if (visy[y])continue;
int tmp = lx[x] + ly[y] - G[x][y];
if (tmp == 0) {
visy[y] = 1;
if (use[y] == -1 || DFS(use[y])) {
use[y] = x; return 1;
}
}
else if (slack[y] > tmp)
slack[y] = tmp;
}
return 0;
}
int km() {
memset(use, -1, sizeof(use));
memset(ly, 0, sizeof(ly));
for (int s = 0; s < n; s++) {
lx[s] = -inf;
for (int w = 0; w < m; w++)
if (G[s][w] > lx[s])
lx[s] = G[s][w];
}
for (int x = 0; x < n; x++) {
for (int s = 0; s < m; s++)
slack[s] = inf;
while (1) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (DFS(x)) break;
int d = inf;
for (int s = 0; s < m; s++)
if (!visy[s] && d > slack[s])
d = slack[s];
for (int s = 0; s < n; s++)
if (visx[s])
lx[s] -= d;
for (int s = 0; s < m; s++)
if (visy[s])ly[s] += d;
else slack[s] -= d;
}
}
int res = 0;
for (int s = 0; s < m; s++)
if (use[s] != -1)
res += G[use[s]][s];
return res;
}
int main() {
while (scanf("%d", &n) == 1) {
for (int s = 0; s < n; s++)
for (int w = 0; w < n; w++)
scanf("%d", &G[s][w]);
m = n;
printf("%d\n", km());
}
return 0;
}
查看17道真题和解析