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
上一篇: 构建OpenCV和Raspberry Pi物体视觉追踪
下一篇: 匹配统计