题解 P3705 【[SDOI2017]新生舞会】
xyz32768
2017-12-03 21:08:13
由于题目求的是最优配对方案，所以很容易想到建一个二分图后用费用流求解，即建立源点和汇点，由源点向每个男生连一条容量为$1$的边，由每个女生向汇点连一条容量为$1$的边，再从任意一个男生向任意一个女生连一条容量为$1$的边。
再考虑费用分配。这时候主要的问题在于$C=\frac{\sum a}{\sum b}$这个式子中$\sum b$在分母位置，无法简单求和。因此可以利用分数规划的思想去掉分母。先二分答案$ans$。
接下来判断最优解$C$能否大于或等于$ans$。把式子$C=\frac{\sum a}{\sum b}$变形后为$\sum a-C\sum b=0$。这时候就可以推出如果$C\geq ans$，就一定存在一种$\sum a,\sum b$的合法分配方案，使得$\sum a-ans\sum b\geq 0$。此时就可以得出，源点连向男生，以及女生连向源点的边的费用都为$0$，第$i$个男生向第$j$个女生的边的费用为$a_{i,j}-ans*b_{i,j}$。建图完成后，如果**最大费用**最大流大于等于$0$，那么$C\geq ans$。
代码：
```cpp
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
const int L = 105, N = 5e5 + 5; const double eps = 1e-8;
int n, a[L][L], b[L][L], ecnt, nxt[N], adj[N], go[N], cap[N], len,
que[N], S, T; double cost[N], dis[N], ans;
bool vis[N], walk[N];
void add_edge(int u, int v, int w, double x) {
nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
cap[ecnt] = w; cost[ecnt] = x;
nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
cap[ecnt] = 0; cost[ecnt] = -x;
}
bool spfa() {
int i; for (i = S; i <= T; i++) dis[i] = -1e20, walk[i] = 0;
dis[que[len = 1] = S] = 0;
for (i = 1; i <= len; i++) {
int u = que[i]; vis[u] = 0;
for (int e = adj[u], v; e; e = nxt[e])
if (cap[e] > 0 && dis[u] + cost[e] > dis[v = go[e]]) {
dis[v] = dis[u] + cost[e];
if (!vis[v]) vis[que[++len] = v] = 1;
}
}
return dis[T] >= -1e19;
}
int dfs(int u, int flow) {
if (u == T) return ans += dis[T] * flow, flow;
int res = 0, delta; walk[u] = 1;
for (int e = adj[u], v; e; e = nxt[e])
if (!walk[v = go[e]] && cap[e] > 0 &&
abs(dis[v] - dis[u] - cost[e]) <= eps) {
delta = dfs(v, min(cap[e], flow - res));
if (delta) {
cap[e] -= delta; cap[e ^ 1] += delta;
res += delta; if (res == flow) break;
}
}
return res;
}
double mcmf() {
ans = 0;
while (spfa()) dfs(S, 0x3f3f3f3f);
return ans;
}
bool check(double mid) {
int i, j; ecnt = S = 1; T = (n << 1) + 2;
for (i = S; i <= T; i++) adj[i] = 0;
for (i = 1; i <= n; i++) add_edge(S, i + 1, 1, 0);
for (i = n + 2; i < T; i++) add_edge(i, T, 1, 0);
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
add_edge(i + 1, j + n + 1, 1, 1.0 * a[i][j] - 1.0 * b[i][j] * mid);
double ap = mcmf(); return abs(ap) <= eps || ap > eps;
}
int main() {
int i, j; n = read();
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
a[i][j] = read();
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
b[i][j] = read();
double l = -1e7, r = 1e7;
while (abs(r - l) > eps) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.6lf\n", r);
return 0;
}
```