[BZOJ 4819][SDOI 2017] 新生舞会

题目大意

给定一个二分图,每个点集各有 $n$ 个节点;再给定两个矩阵 $\{a_{i, j}\}$、$\{b_{i, j}\}$。求二分图的一个完美匹配,使得

最大。

当二分图的点集 $X$ 中的点 $i$ 与点集 $Y$ 中的点 $j$ 匹配时,$a’_i = a_{i, j}, b’_i = b_{i, j}$。

$1 \leqslant n \leqslant 100$

$1 \leqslant a_{i, j}, b_{i, j} \leqslant 10,000$

题目链接

BZOJ 4819

LibreOJ 2003

题解

把那个式子写成 $C \times (b’_1 + b’_2 + \cdots + b’_n) - (a’_1 + a’_2 + \cdots + a’_n) = 0$,二分答案。

具体地说,以 $C \times b_{i, j} - a_{i, j}$ 为边 $X_i - Y_j$ 的权值求最大匹配,若小于等于 $0$,则说明更大。

注意是实数二分。据说固定次数比差小于等于 EPS 要好一点(在控制时间上)。

代码

不要自己搞一个 STL 容器元素的指针!

对于 std::vector ,当容量不够用时,会重新开二倍数组,不一定在原来的位置上,之后指向其内部元素的指针就飞了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <climits>
#include <cfloat>
#include <vector>
#include <queue>
#include <algorithm>
const int MAXN = 105;
struct Edge;
struct Node {
std::vector<Edge> e;
Edge *pre;
int flow;
double dist;
bool inq;
} N[MAXN << 1];
struct Edge {
Node *u, *v;
int cap, flow, rev;
double cost;
Edge() {}
Edge(Node *u, Node *v, int cap, double cost, int rev) : u(u), v(v), cap(cap), flow(0), cost(cost), rev(rev) {}
};
void addEdge(int u, int v, int cap, int cost) {
N[u].e.push_back(Edge(&N[u], &N[v], cap, cost, N[v].e.size()));
N[v].e.push_back(Edge(&N[v], &N[u], 0, -cost, N[u].e.size() - 1));
}
namespace EdmondsKarp {
void solve(int s, int t, int n, int &flow, double &cost) {
flow = 0;
cost = 0;
while (true) {
for (int i = 0; i < n; i++) {
N[i].dist = DBL_MAX;
N[i].flow = 0;
N[i].inq = false;
N[i].pre = NULL;
}
std::queue<Node *> q;
q.push(&N[s]);
N[s].dist = 0;
N[s].flow = INT_MAX;
while (!q.empty()) {
Node *u = q.front();
q.pop();
u->inq = false;
for (Edge *e = &u->e.front(); e && e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->dist > u->dist + e->cost) {
e->v->dist = u->dist + e->cost;
e->v->flow = std::min(u->flow, e->cap - e->flow);
e->v->pre = e;
if (!e->v->inq) {
e->v->inq = true;
q.push(e->v);
}
}
}
}
if (N[t].dist == DBL_MAX) break;
for (Edge *e = N[t].pre; e; e = e->u->pre) {
e->flow += N[t].flow;
e->v->e[e->rev].flow -= N[t].flow;
}
flow += N[t].flow;
cost += N[t].dist * N[t].flow;
}
}
}
int a[MAXN][MAXN], b[MAXN][MAXN], n;
void build() {
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) addEdge(i, j + n, 1, 0);
const int s = 0, t = 2 * n + 1;
for (int i = 1; i <= n; i++) addEdge(s, i, 1, 0), addEdge(n + i, t, 1, 0);
}
bool check(double c) {
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
double temp = c * b[i][j] - a[i][j];
N[i].e[j - 1].cost = temp;
N[j + n].e[N[i].e[j - 1].rev].cost = -temp;
}
const int s = 0, t = 2 * n + 1;
for (int i = s; i < t; i++) for (int j = 0; j < N[i].e.size(); j++)
N[i].e[j].flow = 0;
int flow;
double cost;
EdmondsKarp::solve(s, t, t + 1, flow, cost);
return cost <= 0;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &b[i][j]);
build();
double l = 0, r = 1e4;
for (int i = 0; i < 40; i++) {
double mid = l + (r - l) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.6lf\n", l);
return 0;
}