二分图最大权值完美匹配 hdu2255
程序员文章站
2022-06-07 14:42:49
...
hdu2255
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include <cctype>
#include<functional>
#include<memory.h>
#include<stack>
#include <cassert>
#include<set>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e4+5;
const int mod = 1e9 + 7;
const long long INF = 20050206000;
int n, m, s, t,last=0,cnt=0;
int graph[305][305];
int slack[305],match[305];
bool visp[305], vish[305];
int ex_p[305], ex_h[305];
bool dfs(int u) {
visp[u] = true;
for (int i = 1;i <= n;i++) {
if (vish[i])continue;
int gap = ex_p[u] + ex_h[i] - graph[u][i];
if (gap == 0) {
vish[i] = true;
if (match[i] == -1 || dfs(match[i])) {
match[i] = u;
return true;
}
}
else {
slack[i] = min(slack[i], gap);
}
}
return false;
}
int main() {
while (scanf_s("%d",&n)!=EOF) {
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
scanf_s("%d", &graph[i][j]);
}
}
for (int i = 1;i <= n;i++) {
match[i] = -1;
ex_h[i] = 0;
}
for (int i = 1;i <= n;i++) {
ex_p[i] = graph[i][1];
for (int j = 1;j <= n;j++) {
ex_p[i] = max(ex_p[i], graph[i][j]);
}
}
for (int i = 1;i <= n;i++) {
memset(slack, 0x3f, sizeof slack);
while (1) {
for (int i = 1;i <= n;i++) {
vish[i] = visp[i] = 0;
}
if (dfs(i))break;
int d = 0x3f3f3f3f;
for (int j = 1;j <= n;j++) {
if (!vish[j])d = min(d, slack[j]);
}
for (int j = 1;j <= n;j++) {
if (visp[j])ex_p[j] -= d;
if (vish[j])ex_h[j] += d;
else {
slack[j] -= d;
}
}
}
}
int res = 0;
for (int i = 1;i <= n;i++) {
res += graph[match[i]][i];
}
printf("%d\n", res);
}
}
上一篇: 算法入门篇四 桶排序
下一篇: 竖式问题