欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-07 20:20:25
题目链接解题思路:裸的二分图最大权完美匹配AC代码:#includeusing 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) {l...

题目链接
解题思路:

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

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