P - 奔小康赚大钱 HDU - 2255（二分图最大权完美匹配）

题目链接
解题思路：

• 裸的二分图最大权完美匹配

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 400;
ll n;
ll ka[maxn], kb[maxn], vb[maxn], mb[maxn], c[maxn], p[maxn];
ll graph[maxn][maxn];
void Bfs(ll u) {
	ll a, v = 0, vl = 0, d;
	for(int i = 1; i <= n; i++) p[i] = 0, c[i] = inf;
	mb[v] = u;
	do {
		a = mb[v], d = inf, vb[v] = 1;
		for(int b = 1; b <= n; b++)
			if(!vb[b]) {
				if(c[b] > ka[a] + kb[b] - graph[a][b])
					c[b] = ka[a] + kb[b] - graph[a][b], p[b] = v;
				if(c[b] < d) d = c[b], vl = b;
			}
		for(int b = 0; b <= n; b++)
			if(vb[b]) ka[mb[b]] -= d, kb[b] += d;
			else c[b] -= d;
		v = vl;
	} while(mb[v]);
	while(v) mb[v] = mb[p[v]], v = p[v];
}
ll KM() {
	memset(mb, 0, sizeof(mb));
	memset(ka, 0, sizeof(ka));
	memset(kb, 0, sizeof(kb));
	for(int a = 1; a <= n; a++) {
		memset(vb, 0, sizeof(vb));
		Bfs(a);
	}
	ll res = 0;
	for(int b = 1; b <= n; b++) res += graph[mb[b]][b];
	return res;
}
int main() {
	while(~scanf("%lld", &n)) {
		for(int a = 1; a <= n; a++)
			for(int b = 1; b <= n; b++)
				scanf("%lld", &graph[a][b]);
		printf("%lld\n", KM());
	}
	return 0;
}

本文地址：https://blog.csdn.net/weixin_45691711/article/details/107284709