[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;
}