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

传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有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

有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;
}