题目
题解
其实就是一个KM的板子
KM算法在进行中, 需要满足两个点的顶标值之和大于等于两点之间的边权, 所以进行一次KM即可.
KM之后, 顶标之和就是最小的。因为如果不是最小的，就能通过修改顶标值来使某对顶点的顶标值满足(wx[i]+ly[j]==w[i][j])，这样相等子图中又会多一条边，但此时已全部匹配，所以是最小的。
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 510
using namespace std;
const int inf = 1 << 30;
int s[N][N], lx[N], ly[N], match[N], slack[N], n;
bool vx[N], vy[N];
bool dfs(int u) {
vx[u] = 1;
for (int i = 1; i <= n; i++) {
if (!vy[i]) {
int t = lx[u] + ly[i] - s[u][i];
if (t == 0) {
vy[i] = 1;
if (match[i] == -1 || dfs(mat[i])) {
match[i] = u;
return 1;
}
} else
slack[i] = min(slack[i], t);
}
}
return 0;
}
void KM() {
memset(match, -1, sizeof(match));
memset(ly, 0, sizeof(ly));
for (int i = 1; i <= n; i++) {
lx[i] = -inf;
for (int j = 1; j <= n; j++) lx[i] = max(lx[i], s[i][j]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) slack[j] = inf;
while (1) {
memset(vx, 0, sizeof(vx));
memset(vy, 0, sizeof(vy));
if (dfs(i)) break;
int d = inf;
for (int j = 1; j <= n; j++)
if (!vy[j]) d = min(d, slack[j]);
for (int j = 1; j <= n; j++)
if (vx[j]) lx[j] -= d;
for (int j = 1; j <= n; j++)
if (vy[j]) ly[j] += d;
}
}
int ans = 0;
for (int i = 1; i < n; i++) {
printf("%d ", lx[i]);
ans += lx[i];
}
printf("%d
", lx[n]);
ans += lx[n];
for (int i = 1; i < n; i++) {
printf("%d ", ly[i]);
ans += ly[i];
}
printf("%d
", ly[n]);
ans += ly[n];
printf("%d
", ans);
}
int main() {
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &s[i][j]);
KM();
}
return 0;
}