学校组织了一次新生舞会，Cathy 作为经验丰富的老学姐，负责为同学们安排舞伴。

有 $n$ 个男生和 $n$ 个女生参加舞会，一个男生和一个女生一起跳舞，互为舞伴。
Cathy 收集了这些同学之间的关系，比如两个人之前是否认识，计算得出 $a_{i, j}$ ，表示第 $i$ 个男生和第 $j$ 个女生一起跳舞时他们喜悦程度。
Cathy 还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 $b_{i, j}$ 表示第 $i$ 个男生和第 $j$ 个女生一起跳舞时的不协调裎度。

当然，还需要考虑很多其他间题。

Cathy 想先用一个程序通过 $a_{i, j}$ 和 $b_{i, j}$ 求出一种方案，再手动对方案进行微调。
Cathy 找到你，希望你帮她写那个程序。

一个方案中有 $n$ 对舞伴，假设每对舞伴的喜悦程度分别是 $a'_1, a'_2, \ldots, a'_n$ ，假设每对舞伴不协调程度分别是 $b'_1, b'_2, \ldots, b'_n$ 。令

C = \frac{a'_1 + a'_2 + \cdots + a'_n}{b'_1 + b'_2 + \cdots + b'_n}

Cathy 希望 C 值最大。

题解

题目要求最大化 $\frac {\sum a_i} {\sum b_i}$ ，考虑 $01$ 分数规划。

二分一个答案 $x$ ，假设原式等于 $x$ ，则有：

\frac {\sum a_i} {\sum b_i} = x

移项，得：

\sum a_i - x\sum b_i = 0

同样的，可以得到若原式大于 $x$ 或原式小于 $x$ 的情况。我们求上式最大值以后和 $x$ 比较即可。

最大化移项后的这个式子其实是一个二分图最大权匹配，这里我选择用费用流做法（其实就是不会什么 KM 辣。。）。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cfloat>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
const double EPS = 1e-8;
inline int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    else return x > 0 ? 1 : -1;
}
inline bool equal(double a, double b) {
    return !dcmp(a - b);
}
const int MAX_N = 100;
const int MAX_NODE_NUM = 2 * MAX_N + 2;
const int MAX_EDGE_NUM = 2 * (MAX_N * MAX_N + 2 * MAX_N);
const double NEG_INF = -1e18;
namespace EK {
    struct Node;
    struct Edge;
    struct Edge {
        Node *fr, *to;
        int cap, flow;
        double cost;
        int rev;
        Edge(Node *fr, Node *to, int cap, double cost, int rev) : fr(fr), to(to), cap(cap), flow(0), cost(cost), rev(rev) {}
    };
    struct Node {
        int flow;
        double dist;
        bool inq;
        std::vector<Edge> edges;
        Node *inNode;
        int inEdge;
    } N[MAX_NODE_NUM];
    inline void addEdge(int fr, int to, int cap, double cost) {
        N[fr].edges.push_back(Edge(&N[fr], &N[to], cap, cost, N[to].edges.size()));
        N[to].edges.push_back(Edge(&N[to], &N[fr], 0, -cost, N[fr].edges.size() - 1));
    }
    int n;
    Node *s, *t;
    int maxFlow;
    double minCost;
    inline bool spfa() {
        for (int i = 0; i < n; i++) N[i].dist = NEG_INF;
        std::deque<Node *> q;
        q.push_back(s), s->dist = 0, s->inq = true, s->flow = INT_MAX;
        while (!q.empty()) {
            Node *v = q.front();
            q.pop_front();
            v->inq = false;
            for (int i = 0, n = v->edges.size(); i < n; i++) {
                Edge *e = &v->edges[i];
                if (e->cap > e->flow && e->to->dist < v->dist + e->cost) {
                    e->to->dist = v->dist + e->cost;
                    e->to->inNode = v;
                    e->to->inEdge = i;
                    e->to->flow = std::min(v->flow, e->cap - e->flow);
                    if (!e->to->inq) {
                        e->to->inq = true;
                        if (q.empty() || e->to->dist < q.front()->dist) q.push_front(e->to);
                        else q.push_back(e->to);
                    }
                }
            }
        }
        return !equal(t->dist, NEG_INF);
    }
    inline void argument() {
        int flow = t->flow;
        for (Edge *e = &t->inNode->edges[t->inEdge]; ;) {
            e->flow += flow;
            e->to->edges[e->rev].flow -= flow;
            if (e->fr->inNode) e = &e->fr->inNode->edges[e->fr->inEdge];
            else break;
        }
        maxFlow += flow;
        minCost += t->dist * flow;
    }
    inline void solve(int s, int t, int n) {
        EK::maxFlow = 0, EK::minCost = 0;
        EK::s = &N[s], EK::t = &N[t], EK::n = n;
        while (spfa()) argument();
    }
    inline void clear(int n) {
        for (int i = 0; i < n; i++) N[i].edges.clear();
    }
}
int n;
int a[MAX_N + 1][MAX_N + 1], b[MAX_N + 1][MAX_N + 1];
inline bool check(double bound) {
    EK::clear(n * 2 + 2);
    int s = 0, t = n * 2 + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            EK::addEdge(i, j + n, 1, a[i][j] - bound * b[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) EK::addEdge(s, i, 1, 0);
    for (int i = 1; i <= n; i++) EK::addEdge(i + n, t, 1, 0);
    EK::solve(s, t, n * 2 + 2);
    return dcmp(EK::minCost) >= 0;
}
inline double solve() {
    double l = 0, r = 1e4;
    while (r - l > EPS) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid; else r = mid;
    }
    return (l + r) / 2;
}
int main() {
//	freopen("ball.in", "r", stdin);
//	freopen("ball.out", "w", stdout);
    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]);
    printf("%.6lf\n", solve());
    return 0;
}

「SDOI2017」新生舞会 - 01分数规划，二分图最大权匹配

Contents

题解

代码